kernel/linux
0
Fork 0
mirror of https://git.kernel.org/pub/scm/linux/kernel/git/stable/linux.git/ synced 2026-11-08 18:57:22 +00:00
Code Issues Releases Packages Activity
linux/lib/btree.c

795 lines
19 KiB
Raw Permalink Normal View History

treewide: Replace GPLv2 boilerplate/reference with SPDX - rule 431 Based on 1 normalized pattern(s): as should be obvious for linux kernel code license is gplv2 extracted by the scancode license scanner the SPDX license identifier GPL-2.0-only has been chosen to replace the boilerplate/reference in 1 file(s). Signed-off-by: Thomas Gleixner <tglx@linutronix.de> Reviewed-by: Allison Randal <allison@lohutok.net> Reviewed-by: Armijn Hemel <armijn@tjaldur.nl> Cc: linux-spdx@vger.kernel.org Link: https://lkml.kernel.org/r/20190531190114.565827206@linutronix.de Signed-off-by: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
2019-06-01 10:08:45 +02:00
[LogFS] add new flash file system This is a new flash file system. See Documentation/filesystems/logfs.txt Signed-off-by: Joern Engel <joern@logfs.org>
2009-11-20 20:13:39 +01:00
btree: avoid variable-length allocations geo->keylen cannot be larger than 4. So we might as well make fixed-size allocations. Given the one remaining user, geo->keylen cannot even be larger than 1. Logfs used to have 64bit and 128bit keys, tcm_qla2xxx only has 32bit keys. But let's not break the code if we don't have to. Signed-off-by: Joern Engel <joern@purestorage.com> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
2018-03-13 11:36:49 -07:00
[LogFS] add new flash file system This is a new flash file system. See Documentation/filesystems/logfs.txt Signed-off-by: Joern Engel <joern@logfs.org>
2009-11-20 20:13:39 +01:00
treewide: Remove old email address There were still a number of references to my old Red Hat email address in the kernel source. Remove these while keeping the Red Hat copyright notices intact. Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org> Cc: Arnaldo Carvalho de Melo <acme@redhat.com> Cc: Jiri Olsa <jolsa@redhat.com> Cc: Linus Torvalds <torvalds@linux-foundation.org> Cc: Mike Galbraith <efault@gmx.de> Cc: Peter Zijlstra <peterz@infradead.org> Cc: Stephane Eranian <eranian@google.com> Cc: Thomas Gleixner <tglx@linutronix.de> Cc: Vince Weaver <vincent.weaver@maine.edu> Signed-off-by: Ingo Molnar <mingo@kernel.org>
2015-11-16 11:08:45 +01:00
[LogFS] add new flash file system This is a new flash file system. See Documentation/filesystems/logfs.txt Signed-off-by: Joern Engel <joern@logfs.org>
2009-11-20 20:13:39 +01:00
Fix common misspellings Fixes generated by 'codespell' and manually reviewed. Signed-off-by: Lucas De Marchi <lucas.demarchi@profusion.mobi>
2011-03-30 22:57:33 -03:00
[LogFS] add new flash file system This is a new flash file system. See Documentation/filesystems/logfs.txt Signed-off-by: Joern Engel <joern@logfs.org>
2009-11-20 20:13:39 +01:00
btree: avoid variable-length allocations geo->keylen cannot be larger than 4. So we might as well make fixed-size allocations. Given the one remaining user, geo->keylen cannot even be larger than 1. Logfs used to have 64bit and 128bit keys, tcm_qla2xxx only has 32bit keys. But let's not break the code if we don't have to. Signed-off-by: Joern Engel <joern@purestorage.com> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
2018-03-13 11:36:49 -07:00
[LogFS] add new flash file system This is a new flash file system. See Documentation/filesystems/logfs.txt Signed-off-by: Joern Engel <joern@logfs.org>
2009-11-20 20:13:39 +01:00
lib/btree: fix possible NULL pointer dereference mempool_alloc() can return null in atomic case. Signed-off-by: Denis Kirjanov <kirjanov@gmail.com> Cc: Joern Engel <joern@logfs.org> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
2010-05-15 12:32:34 -04:00
[LogFS] add new flash file system This is a new flash file system. See Documentation/filesystems/logfs.txt Signed-off-by: Joern Engel <joern@logfs.org>
2009-11-20 20:13:39 +01:00
lib/btree.c: fix leak of whole btree nodes I use btree from 3.14-rc2 in my own module. When the btree module is removed, a warning arises: kmem_cache_destroy btree_node: Slab cache still has objects CPU: 13 PID: 9150 Comm: rmmod Tainted: GF O 3.14.0-rc2 #1 Hardware name: Inspur NF5270M3/NF5270M3, BIOS CHEETAH_2.1.3 09/10/2013 Call Trace: dump_stack+0x49/0x5d kmem_cache_destroy+0xcf/0xe0 btree_module_exit+0x10/0x12 [btree] SyS_delete_module+0x198/0x1f0 system_call_fastpath+0x16/0x1b The cause is that it doesn't release the last btree node, when height = 1 and fill = 1. [akpm@linux-foundation.org: remove unneeded test of NULL] Signed-off-by: Minfei Huang <huangminfei@ucloud.cn> Cc: Joern Engel <joern@logfs.org> Cc: Johannes Berg <johannes@sipsolutions.net> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
2014-06-04 16:11:53 -07:00
[LogFS] add new flash file system This is a new flash file system. See Documentation/filesystems/logfs.txt Signed-off-by: Joern Engel <joern@logfs.org>
2009-11-20 20:13:39 +01:00
lib/btree: simplify btree_{lookup|update} btree_{lookup|update} both need to look up node by key, using the common parts(add function btree_lookup_node) to simplify code. Link: https://lkml.kernel.org/r/20220607133556.34732-1-wuchi.zero@gmail.com Signed-off-by: wuchi <wuchi.zero@gmail.com> Cc: Peter Zijlstra (Intel) <peterz@infradead.org> Cc: Arnaldo Carvalho de Melo <acme@redhat.com> Cc: Jiri Olsa <jolsa@redhat.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
2022-06-07 21:35:56 +08:00
[LogFS] add new flash file system This is a new flash file system. See Documentation/filesystems/logfs.txt Signed-off-by: Joern Engel <joern@logfs.org>
2009-11-20 20:13:39 +01:00
lib/btree: simplify btree_{lookup|update} btree_{lookup|update} both need to look up node by key, using the common parts(add function btree_lookup_node) to simplify code. Link: https://lkml.kernel.org/r/20220607133556.34732-1-wuchi.zero@gmail.com Signed-off-by: wuchi <wuchi.zero@gmail.com> Cc: Peter Zijlstra (Intel) <peterz@infradead.org> Cc: Arnaldo Carvalho de Melo <acme@redhat.com> Cc: Jiri Olsa <jolsa@redhat.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
2022-06-07 21:35:56 +08:00
[LogFS] add new flash file system This is a new flash file system. See Documentation/filesystems/logfs.txt Signed-off-by: Joern Engel <joern@logfs.org>
2009-11-20 20:13:39 +01:00
lib/btree: simplify btree_{lookup|update} btree_{lookup|update} both need to look up node by key, using the common parts(add function btree_lookup_node) to simplify code. Link: https://lkml.kernel.org/r/20220607133556.34732-1-wuchi.zero@gmail.com Signed-off-by: wuchi <wuchi.zero@gmail.com> Cc: Peter Zijlstra (Intel) <peterz@infradead.org> Cc: Arnaldo Carvalho de Melo <acme@redhat.com> Cc: Jiri Olsa <jolsa@redhat.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
2022-06-07 21:35:56 +08:00
[LogFS] add new flash file system This is a new flash file system. See Documentation/filesystems/logfs.txt Signed-off-by: Joern Engel <joern@logfs.org>
2009-11-20 20:13:39 +01:00
lib/btree: simplify btree_{lookup|update} btree_{lookup|update} both need to look up node by key, using the common parts(add function btree_lookup_node) to simplify code. Link: https://lkml.kernel.org/r/20220607133556.34732-1-wuchi.zero@gmail.com Signed-off-by: wuchi <wuchi.zero@gmail.com> Cc: Peter Zijlstra (Intel) <peterz@infradead.org> Cc: Arnaldo Carvalho de Melo <acme@redhat.com> Cc: Jiri Olsa <jolsa@redhat.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
2022-06-07 21:35:56 +08:00
[LogFS] add new flash file system This is a new flash file system. See Documentation/filesystems/logfs.txt Signed-off-by: Joern Engel <joern@logfs.org>
2009-11-20 20:13:39 +01:00
lib/btree: simplify btree_{lookup|update} btree_{lookup|update} both need to look up node by key, using the common parts(add function btree_lookup_node) to simplify code. Link: https://lkml.kernel.org/r/20220607133556.34732-1-wuchi.zero@gmail.com Signed-off-by: wuchi <wuchi.zero@gmail.com> Cc: Peter Zijlstra (Intel) <peterz@infradead.org> Cc: Arnaldo Carvalho de Melo <acme@redhat.com> Cc: Jiri Olsa <jolsa@redhat.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
2022-06-07 21:35:56 +08:00
[LogFS] add new flash file system This is a new flash file system. See Documentation/filesystems/logfs.txt Signed-off-by: Joern Engel <joern@logfs.org>
2009-11-20 20:13:39 +01:00
btree: avoid variable-length allocations geo->keylen cannot be larger than 4. So we might as well make fixed-size allocations. Given the one remaining user, geo->keylen cannot even be larger than 1. Logfs used to have 64bit and 128bit keys, tcm_qla2xxx only has 32bit keys. But let's not break the code if we don't have to. Signed-off-by: Joern Engel <joern@purestorage.com> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
2018-03-13 11:36:49 -07:00
[LogFS] add new flash file system This is a new flash file system. See Documentation/filesystems/logfs.txt Signed-off-by: Joern Engel <joern@logfs.org>
2009-11-20 20:13:39 +01:00
btree: fix tree corruption in btree_get_prev() The memory the parameter __key points to is used as an iterator in btree_get_prev(), so if we save off a bkey() pointer in retry_key and then assign that to __key, we'll end up corrupting the btree internals when we do eg longcpy(__key, bkey(geo, node, i), geo->keylen); to return the key value. What we should do instead is use longcpy() to copy the key value that retry_key points to __key. This can cause a btree to get corrupted by seemingly read-only operations such as btree_for_each_safe. [akpm@linux-foundation.org: avoid the double longcpy()] Signed-off-by: Roland Dreier <roland@purestorage.com> Acked-by: Joern Engel <joern@logfs.org> Cc: <stable@vger.kernel.org> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
2012-06-07 14:21:13 -07:00
[LogFS] add new flash file system This is a new flash file system. See Documentation/filesystems/logfs.txt Signed-off-by: Joern Engel <joern@logfs.org>
2009-11-20 20:13:39 +01:00
btree: fix tree corruption in btree_get_prev() The memory the parameter __key points to is used as an iterator in btree_get_prev(), so if we save off a bkey() pointer in retry_key and then assign that to __key, we'll end up corrupting the btree internals when we do eg longcpy(__key, bkey(geo, node, i), geo->keylen); to return the key value. What we should do instead is use longcpy() to copy the key value that retry_key points to __key. This can cause a btree to get corrupted by seemingly read-only operations such as btree_for_each_safe. [akpm@linux-foundation.org: avoid the double longcpy()] Signed-off-by: Roland Dreier <roland@purestorage.com> Acked-by: Joern Engel <joern@logfs.org> Cc: <stable@vger.kernel.org> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
2012-06-07 14:21:13 -07:00
[LogFS] add new flash file system This is a new flash file system. See Documentation/filesystems/logfs.txt Signed-off-by: Joern Engel <joern@logfs.org>
2009-11-20 20:13:39 +01:00
btree: export btree_get_prev() so modules can use btree_for_each The btree_for_each API is implemented with macros that internally call btree_get_prev(), so if btree_get_prev() isn't exported then modules fail to link if they try to use one of the btree_for_each macros. Since the rest of the btree API is exported, we should keep things orthogonal and make this work too. Signed-off-by: Roland Dreier <roland@purestorage.com> Signed-off-by: Steve Hodgson <steve@purestorage.com> Acked-by: Joern Engel <joern@logfs.org> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
2012-01-10 15:09:47 -08:00
[LogFS] add new flash file system This is a new flash file system. See Documentation/filesystems/logfs.txt Signed-off-by: Joern Engel <joern@logfs.org>
2009-11-20 20:13:39 +01:00
btree: catch NULL value before it does harm Storing NULL values in the btree is illegal and can lead to memory corruption and possible other fun as well. Catch it on insert, instead of waiting for the inevitable. Signed-off-by: Joern Engel <joern@logfs.org> Signed-off-by: Roland Dreier <roland@purestorage.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
2012-06-07 14:21:14 -07:00
[LogFS] add new flash file system This is a new flash file system. See Documentation/filesystems/logfs.txt Signed-off-by: Joern Engel <joern@logfs.org>
2009-11-20 20:13:39 +01:00
Fix common misspellings Fixes generated by 'codespell' and manually reviewed. Signed-off-by: Lucas De Marchi <lucas.demarchi@profusion.mobi>
2011-03-30 22:57:33 -03:00
[LogFS] add new flash file system This is a new flash file system. See Documentation/filesystems/logfs.txt Signed-off-by: Joern Engel <joern@logfs.org>
2009-11-20 20:13:39 +01:00
btree: avoid variable-length allocations geo->keylen cannot be larger than 4. So we might as well make fixed-size allocations. Given the one remaining user, geo->keylen cannot even be larger than 1. Logfs used to have 64bit and 128bit keys, tcm_qla2xxx only has 32bit keys. But let's not break the code if we don't have to. Signed-off-by: Joern Engel <joern@purestorage.com> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
2018-03-13 11:36:49 -07:00
[LogFS] add new flash file system This is a new flash file system. See Documentation/filesystems/logfs.txt Signed-off-by: Joern Engel <joern@logfs.org>
2009-11-20 20:13:39 +01:00
btree: simplify merge logic by using btree_last() return value Previously btree_merge() called btree_last() only to test existence, then performed an extra btree_lookup() to fetch the value. This patch changes it to directly use the value returned by btree_last(), avoiding redundant lookups and simplifying the merge loop. Link: https://lkml.kernel.org/r/20250826161741.686704-1-409411716@gms.tku.edu.tw Signed-off-by: Guan-Chun Wu <409411716@gms.tku.edu.tw> Cc: Kuan-Wei Chiu <visitorckw@gmail.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
2025-08-27 00:17:41 +08:00
[LogFS] add new flash file system This is a new flash file system. See Documentation/filesystems/logfs.txt Signed-off-by: Joern Engel <joern@logfs.org>
2009-11-20 20:13:39 +01:00