Liam R. Howlett [Fri, 15 Mar 2019 20:01:22 +0000 (16:01 -0400)]
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>
Liam R. Howlett [Wed, 13 Feb 2019 16:12:02 +0000 (11:12 -0500)]
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>
Liam R. Howlett [Thu, 7 Feb 2019 19:34:49 +0000 (14:34 -0500)]
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>
Liam R. Howlett [Thu, 31 Jan 2019 16:11:13 +0000 (11:11 -0500)]
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>
Liam R. Howlett [Tue, 29 Jan 2019 20:06:00 +0000 (15:06 -0500)]
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>
Liam R. Howlett [Thu, 10 Jan 2019 20:18:01 +0000 (15:18 -0500)]
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>
Liam R. Howlett [Wed, 9 Jan 2019 20:11:15 +0000 (15:11 -0500)]
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>
Liam R. Howlett [Mon, 7 Jan 2019 19:45:10 +0000 (14:45 -0500)]
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>
Liam R. Howlett [Mon, 7 Jan 2019 17:46:05 +0000 (12:46 -0500)]
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>
Liam R. Howlett [Thu, 3 Jan 2019 18:30:57 +0000 (13:30 -0500)]
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>
Matthew Wilcox [Mon, 24 Dec 2018 15:27:45 +0000 (10:27 -0500)]
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>
Merge tag 'meminit-v5.3-rc2' of git://git.kernel.org/pub/scm/linux/kernel/git/kees/linux
Pull structleak fix from Kees Cook:
"Disable gcc-based stack variable auto-init under KASAN (Arnd
Bergmann).
This fixes a bunch of build warnings under KASAN and the
gcc-plugin-based stack auto-initialization features (which are
arguably redundant, so better to let KASAN control this)"
* tag 'meminit-v5.3-rc2' of git://git.kernel.org/pub/scm/linux/kernel/git/kees/linux:
structleak: disable STRUCTLEAK_BYREF in combination with KASAN_STACK
Merge tag 'char-misc-5.3-rc2' of git://git.kernel.org/pub/scm/linux/kernel/git/gregkh/char-misc
Pull char/misc driver fixes from Greg KH:
"Here are some small char and misc driver fixes for 5.3-rc2 to resolve
some reported issues.
Nothing major at all, some binder bugfixes for issues found, some new
mei device ids, firmware building warning fixes, habanalabs fixes, a
few other build fixes, and a MAINTAINERS update.
All of these have been in linux-next with no reported issues"
* tag 'char-misc-5.3-rc2' of git://git.kernel.org/pub/scm/linux/kernel/git/gregkh/char-misc:
test_firmware: fix a memory leak bug
hpet: Fix division by zero in hpet_time_div()
eeprom: make older eeprom drivers select NVMEM_SYSFS
vmw_balloon: Remove Julien from the maintainers list
fpga-manager: altera-ps-spi: Fix build error
mei: me: add mule creek canyon (EHL) device ids
binder: prevent transactions to context manager from its own process.
binder: Set end of SG buffer area properly.
firmware: Fix missing inline
firmware: fix build errors in paged buffer handling code
habanalabs: don't reset device when getting VRHOT
habanalabs: use %pad for printing a dma_addr_t
Merge tag 'tty-5.3-rc2' of git://git.kernel.org/pub/scm/linux/kernel/git/gregkh/tty
Pull tty fixes from Greg KH:
"Here are two tty/vt fixes:
- delete the netx-serial driver as the arch has been removed, no need
to keep the serial driver for it around either.
- vt console_lock fix to resolve a reported noisy warning at runtime
Both of these have been in linux-next with no reported issues"
* tag 'tty-5.3-rc2' of git://git.kernel.org/pub/scm/linux/kernel/git/gregkh/tty:
vt: Grab console_lock around con_is_bound in show_bind
tty: serial: netx: Delete driver
Merge tag 'spdx-5.3-rc2' of git://git.kernel.org/pub/scm/linux/kernel/git/gregkh/spdx
Pull SPDX fixes from Greg KH:
"Here are some small SPDX fixes for 5.3-rc2 for things that came in
during the 5.3-rc1 merge window that we previously missed.
Only three small patches here:
- two uapi patches to resolve some SPDX tags that were not correct
- fix an invalid SPDX tag in the iomap Makefile file
All have been properly reviewed on the public mailing lists"
* tag 'spdx-5.3-rc2' of git://git.kernel.org/pub/scm/linux/kernel/git/gregkh/spdx:
iomap: fix Invalid License ID
treewide: remove SPDX "WITH Linux-syscall-note" from kernel-space headers again
treewide: add "WITH Linux-syscall-note" to SPDX tag of uapi headers
projects / users / jedix / linux-maple.git / log