maple_tree: Add mas_pause for pausing iterator.

Also add testcases for the pause function.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

maple_tree: checkpatch fixes

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

maple_tree: Add restarts for interaters on dead nodes.

also fix the testcase for the iterators for the zero entry test.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

maple_tree: mt_for_each implementation

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

maple_tree: Add check for mas_for_each loop.

Also change the ams_start to reset min/max

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

mas_find implementation

Fixes for prev/next node as well

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

maple_tree: mas_next_node/mas_prev_node restarts added on dead node detection.

Also required reordering some functions.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

maple_tree: Add basic store support.

This store operation builds a new tree.  This was done to avoid creating
an invalid b-tree (not the same height from all leaves to head).

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

maple_tree: Change erase return to 0 on success.

Count isn't used, so return 0 for success.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

maple_tree: Add reverse walk.

Search for a hole of a given size at the highest address.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

maple_tree: Fix range checking on skip_node

When skipping a node, it is only valid to break out of the loop if slot
+ 1 is valid.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

maple_tree: Fix forward searching for gaps.

There was an off-by-one issue with the gap calculation as it is
exclusive - inclusive.

Fix the ascend search in maple_awalk using the wrong parent slot.

Return -EBUSY correctly when a failure occurs.

Fix node splitting when there is no such thing as dense.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

maple_dump: Pad better

I think this works out better visually than the previous effort.

Signed-off-by: Matthew Wilcox <willy@infradead.org>

maple_dump: Pad to indicate depth

Not entirely sure if this is the best way to indicate depth; let's
try it for a bit and see how confused we get.

Signed-off-by: Matthew Wilcox <willy@infradead.org>

maple_tree: Disable dense nodes.

Disable dense nodes to avoid split issues.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

maple_tree: messy test output

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

maple_tree: Remove early exit on tests

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

maple_tree: Add awalk for walking allocation trees for gaps.

Adds mtree_alloc_range to allocate a range.  Some basic tests.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

maple_tree: Add maple_tree alloc support for gaps.

Start populating gaps with values
Remove the maple_aleaf_64 type and use regular maple_leaf_64.
Rework pivot calculations to be more straight forward.
Don't use dense nodes in the root node to avoid having a dense node as
the right-most node.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

maple_tree: typedef maple_enode for encoded node.

Use the compiler to check if an encoded node or a regular node is used

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

maple_tree: typedef parent node to maple_pnode

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

maple_tree: Use encoded node for getting rcu slot in ma_encoded_parent

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

maple_tree: Add initial maple_arange_64 node support.

maple_arange_64 is for allocation ranges which need to track gaps in
subtrees.  This commit does not address tracking the gaps.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

test_maple_tree: Fix range checking.

Checking a range was not using the correct number range.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

maple_tree: Fix range add to empty tree.

When adding to an empty tree, use the encoded node to set the pivot.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

maple_tree: Rework internal walk.

Reduce possible calls to get an rcu entry.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

ma_xa_benchmark: Update time calculations

Time calculations were prone to overflow because seconds were not
included.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

maple_tree: Fix double free error.

There was a double free which raced with the rcu free so it was not
detected all the time.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

maple: Fix _mas_walk return & clean up ma_insert root expand logic

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

maple: Fix off by one error when walking.

When going to the next slot, the minimum value is actually pivot + 1 and
not just the pivot value.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

maple_tree: Optimize _mas_walk

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

maple_tree: Rework walk.

Make walk more efficient by avoiding duplicate fetches of slot and pivots.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

maple_tree: Make walk faster.

Avoid looking up duplicate information.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

ma_xa_benchmark: Fix percentage calculation for time.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

maple_tree: Efficiencies

Remove unneeded code.
Fix splitting from the back of a node.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

maple_tree: Dense node support & nulls in tree.

Support dense node types.  The reduces the space required for sequential
indexes a lot.
Splitting now decides between usign the parent type and the dense node
type for left/right independently.
Fixes had to be made to pivot lookups.
A few static inline additions to speed things up.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

maple_tree:  Performance enhancements.

Start using slot 0 on splits.
Fix missing breaks on set of slots.
Calc node type only once during certain loops

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

maple_tree: Make functions node-type generic.

Move mt_max outside of debug and add mt_slots
Create mt_slots for enum to slot size mapping.
Rename ma_cp_data_64 to ma_split_data
Drop extra calls in split.
Create calls to get/set pivots & slots.
Rework all functions to use generic calls.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

ma_xa_benchmark: Use user time. add rcu barrier before size calc.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

ma_xa_benchmark: Initial push

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

maple_tree: remove duplicate function.

When adding a check for reserved entries, I hadn't noticed it already
existed.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

test_maple_tree: Fix comments & add more tests.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

maple_tree: Fix split & insert to use last slot.

The last slot was revealed to be NULL always.  Fix this by changing the
the end calculations and to ensure it is okay to use the final slot.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

maple_tree: Drop depth from split operation.

It is not used.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

maple_tree: Fix root bit & parent type.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

maple_tree: fix goto lables in ma_insert

Fix the order of goto labels and set the error correct if using exists.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

maple_tree: Add root expand to node if the single entry ends in 10.

As requested by page cache.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

maple_tree: Change mask calc for mt_parent_type

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

maple_tree: Remove depth from ma_split.

the depth is no longer use, so drop it.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

Thoughts: Add table of bits in the parent.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

maple_tree: Fix parent definitions & fallout from ULONG_MAX ending.

coalesce needed to be updated for ULONG_MAX endings.
ma_copy needed to check for ULONG_MAX ending.
ma_encoded_parent no longer updates the ma_state limits.
adopt_children needed the encoded node passed in for the node type to
encode in the parent of the children.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

test_maple_tree: Add seqential test for adding 1000 entries

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

maple_tree: Add comment about encode parent.

function name seems to lack description

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

maple_tree: Move mas_update_limits

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

maple_tree: Small cleanup of code and comments

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

maple_tree: Fix error in splitting on the right side

When splitting on the right side, there were a number of logical
errors:
1. Finding the parents type needed the parent to be encoded, so move the
logic to a location better suited to use the encoded node.
2. ma_copy had an incorrect range (off by one).
3. mt_replace was not using the encoded node to find the parent's slot.
This would always return zero.
4. ma_link had a potential overflow in the pivot.
5. The ma_state's min/max was not being updated and so the pivots were
not always correct when using the min/max.
6. The data end detection needed to be updated to also check for
ULONG_MAX.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

test_maple_tree: port nomem thread race test.

Test to see that allocations work when two threads are racing.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

maple_tree: Change return type of ma_insert.

ma_insert was returning a pointer in the old API.  This is no longer
needed.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

test_maple_tree: Re-implement old allocation tests for new API.

Rewrite the allocation tests for maple2 rewrite.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

testing: Fix bug in allocation tests for radix-tree linux.

When initializing kmem_cache for testing, ensure non_kernel is
initialized to zero.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

test_maple_tree: Fix compile warning

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

maple_tree: Clean up erase function.

The node type is set during the partial copy of data operation now.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

maple_tree: Remove enc_full and just use mas->node.

No need for this variable in mas_split.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

maple_tree: Load safe root to mas->node in encoded_parent

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

maple_tree: Code clean up.

Drop unused variables & a fuction left from development of split

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

maple_tree: Fix dump debug code when the last slot is null.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

maple_node: Fix comments

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

maple_tree: Split support

Initial split support.  Walks up the tree splitting as necessary to
support the addition of a node.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

maple_tree: Rearrange _ma_insert for appends.

Reorder and make _ma_insert append safe and prepare for split.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

maple_tree: Refactor coalesce into a separate function.

Reworked logic to have a bit of a cleaner looking function.  Supports
full nodes now as well.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

maple_tree: Avoid allocating a node in coalescing until necessary

When looping through a node, don't create a new node if there is no need
to do so.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

maple_tree: Avoid coalescing on insert if it is not needed.

On insert, iterate over the pivots looking for matching ones to
determine if slots need to be coalesced.
Erase always needs to coalesce, so don't check there.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

maple_tree: whitespace fix

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

test_maple_tree: Add new function to allow __GFP_DIRECT_RECLAIM gfp for
a given number of times.

Set a variable that allows reclaims to occur for a specific count for
testing.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

maple_tree: Change ma_coalesce to return the number of slots removed.

Set ma->node to the new node, so save the previous node before calling
the function.  Also fix an off-by-one error in ma_coalesce.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

Corrected typo

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

maple_tree: Add erase support.

Refactor replacing a node in a tree to its own function and use that
with the erase and insert functions.

Erase NULLs the range in which the index resides and coalesces adjacent
NULLs if allocation succeeds.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

maple_tree: Fix several off-by-one errors.

When counting through the slots/pivots, the pivots overflow before the
slots which is an area of confusion sometimes.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

maple_tree: Rework walking the tree to combine insert/walk/erase
functions.

This turned out to be a huge deal with many issues resolved for the
following of Thoughts:

1. Nodes can use the last 0x7F bits of the address, so clear them and
such.
2. Root needs to have bit 1 (0x2) set, so be safe around that.
3. mas->node should be encoded (except root needs to remove bit 1 to
avoid being seen as an error).
4. xa_is_node no longer works, so remove BUG_ONs.  Take care that we
know we have a value when we have a slot & an leaf node in mas->node.
5. Store slots in the same place as the alloc requests as their uses do
not overlap.
6. mas_start needs to return a safe root instead of making its own node.
7. Insert was basically rewritten
8. Verify that we are no inserting reserved values
9. Change testcases to not try to insert reserved values.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

maple_tree: Fix potential race condition in _ma_insert

The pivots protect readers from reading invalid data.  Without a wmb
between overwriting the end pivot (of zero), there is a potential that
the writes could be reordered and a race condition would exist between
updating both values and a reader interleaving those writes.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

maple_tree: Add insert/append operation.

Check for NULL runs by looking for duplicate pivots and coalesce them
into a single entry.  Append and insert into a new node, then replace
the old node and adopt the children.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

maple_tree: Fix data_end calculation and root expansion.

Root expansion needs to set the pivot to the empty value if there is no
zero for the append to function correctly.

In append, we know the data end will always be at least 1, so take two
off the idx when checking the previous pivot value (since we also add 1
to the end for the new termination).

Append will need to be altered to cover off the overflow possibility in
the future.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

maple_tree: clean up swithc statement and remove null parent assignment

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

More Thoughts

Mostly relating to auxiliary data

Signed-off-by: Matthew Wilcox <willy@infradead.org>

maple_tree: Implement destroy.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

maple_tree: Implement expanding root.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

maple_tree: Add kmem_cache

Allocate nodes from a kmem cache, making the necessary changes to the
slab emulation to support alignment.  Free nodes through RCU.

Signed-off-by: Matthew Wilcox <willy@infradead.org>

maple_tree: Change my thoughts

Reorganise the Thoughts file to bring it to some kind of order, and
change the tree dumping code accordingly.  It only supports three kinds
of node so far: leaf_64, range_64 and dense.  But it does now support
user pointers that are only 2-byte aligned.

Signed-off-by: Matthew Wilcox <willy@infradead.org>

Add some notes

Not for upstream, obviously

maple_tree: Fix mt_dump

Conform to new definition of maple tree

Signed-off-by: Matthew Wilcox <willy@infradead.org>

maple_tree: Fix compilation differently

Signed-off-by: Matthew Wilcox <willy@infradead.org>

maple_tree: Testing framework and stubbed out maple_tree.c

Also fix some compile issues with header.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

maple_tree: Add header file

Signed-off-by: Matthew Wilcox <willy@infradead.org>

Linux 5.10

Merge tag 'x86-urgent-2020-12-13' of git://git.kernel.org/pub/scm/linux/kernel/git/tip/tip

Pull x86 fixes from Thomas Gleixner:
 "A set of x86 and membarrier fixes:

   - Correct a few problems in the x86 and the generic membarrier
     implementation. Small corrections for assumptions about visibility
     which have turned out not to be true.

   - Make the PAT bits for memory encryption correct vs 4K and 2M/1G
     page table entries as they are at a different location.

   - Fix a concurrency issue in the the local bandwidth readout of
     resource control leading to incorrect values

   - Fix the ordering of allocating a vector for an interrupt. The order
     missed to respect the provided cpumask when the first attempt of
     allocating node local in the mask fails. It then tries the node
     instead of trying the full provided mask first. This leads to
     erroneous error messages and breaking the (user) supplied affinity
     request. Reorder it.

   - Make the INT3 padding detection in optprobe work correctly"

* tag 'x86-urgent-2020-12-13' of git://git.kernel.org/pub/scm/linux/kernel/git/tip/tip:
  x86/kprobes: Fix optprobe to detect INT3 padding correctly
  x86/apic/vector: Fix ordering in vector assignment
  x86/resctrl: Fix incorrect local bandwidth when mba_sc is enabled
  x86/mm/mem_encrypt: Fix definition of PMD_FLAGS_DEC_WP
  membarrier: Execute SYNC_CORE on the calling thread
  membarrier: Explicitly sync remote cores when SYNC_CORE is requested
  membarrier: Add an actual barrier before rseq_preempt()
  x86/membarrier: Get rid of a dubious optimization

Merge tag 'block-5.10-2020-12-12' of git://git.kernel.dk/linux-block

Pull block fixes from Jens Axboe:
 "This should be it for 5.10.

  Mike and Song looked into the warning case, and thankfully it appears
  the fix was pretty trivial - we can just change the md device chunk
  type to unsigned int to get rid of it. They cannot currently be < 0,
  and nobody is checking for that either.

  We're reverting the discard changes as the corruption reports came in
  very late, and there's just no time to attempt to deal with it at this
  point. Reverting the changes in question is the right call for 5.10"

* tag 'block-5.10-2020-12-12' of git://git.kernel.dk/linux-block:
  md: change mddev 'chunk_sectors' from int to unsigned
  Revert "md: add md_submit_discard_bio() for submitting discard bio"
  Revert "md/raid10: extend r10bio devs to raid disks"
  Revert "md/raid10: pull codes that wait for blocked dev into one function"
  Revert "md/raid10: improve raid10 discard request"
  Revert "md/raid10: improve discard request for far layout"
  Revert "dm raid: remove unnecessary discard limits for raid10"

Merge tag 'scsi-fixes' of git://git.kernel.org/pub/scm/linux/kernel/git/jejb/scsi

Pull SCSI fixes from James Bottomley:
 "Five small fixes.  Four in drivers:

   - hisi_sas: fix internal queue timeout

   - be2iscsi: revert a prior fix causing problems

   - bnx2i: add missing dependency

   - storvsc: late arriving revert of a problem fix

  and one in the core.

  The core one is a minor change to stop paying attention to the busy
  count when returning out of resources because there's a race window
  where the queue might not restart due to missing returning I/O"

* tag 'scsi-fixes' of git://git.kernel.org/pub/scm/linux/kernel/git/jejb/scsi:
  Revert "scsi: storvsc: Validate length of incoming packet in storvsc_on_channel_callback()"
  scsi: hisi_sas: Select a suitable queue for internal I/Os
  scsi: core: Fix race between handling STS_RESOURCE and completion
  scsi: be2iscsi: Revert "Fix a theoretical leak in beiscsi_create_eqs()"
  scsi: bnx2i: Requires MMU

Merge branch 'i2c/for-current' of git://git.kernel.org/pub/scm/linux/kernel/git/wsa/linux

Pull i2c fix from Wolfram Sang:
 "Bugfix for the AT24 EEPROM driver"

* 'i2c/for-current' of git://git.kernel.org/pub/scm/linux/kernel/git/wsa/linux:
  misc: eeprom: at24: fix NVMEM name with custom AT24 device name

Merge tag 'for-linus' of git://git.kernel.org/pub/scm/virt/kvm/kvm

Pull kvm fixes from Paolo Bonzini:
 "Bugfixes for ARM, x86 and tools"

* tag 'for-linus' of git://git.kernel.org/pub/scm/virt/kvm/kvm:
  tools/kvm_stat: Exempt time-based counters
  KVM: mmu: Fix SPTE encoding of MMIO generation upper half
  kvm: x86/mmu: Use cpuid to determine max gfn
  kvm: svm: de-allocate svm_cpu_data for all cpus in svm_cpu_uninit()
  selftests: kvm/set_memory_region_test: Fix race in move region test
  KVM: arm64: Add usage of stage 2 fault lookup level in user_mem_abort()
  KVM: arm64: Fix handling of merging tables into a block entry
  KVM: arm64: Fix memory leak on stage2 update of a valid PTE

Merge tag 'for-linus-5.10c-rc8-tag' of git://git.kernel.org/pub/scm/linux/kernel/git/xen/tip

Pull xen fixes from Juergen Gross:
 "A short series fixing a regression introduced in 5.9 for running as
  Xen dom0 on a system with NVMe backed storage"

* tag 'for-linus-5.10c-rc8-tag' of git://git.kernel.org/pub/scm/linux/kernel/git/xen/tip:
  xen: don't use page->lru for ZONE_DEVICE memory
  xen: add helpers for caching grant mapping pages