linux-kernel - Re: [PATCH] add b+tree library

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <20090110115626.GC20611@logfs.org>
Date:	Sat, 10 Jan 2009 12:56:27 +0100
From:	Jörn Engel <joern@...fs.org>
To:	Johannes Berg <johannes@...solutions.net>
Cc:	KOSAKI Motohiro <kosaki.motohiro@...fujitsu.com>,
	Andrew Morton <akpm@...ux-foundation.org>,
	Linux Kernel list <linux-kernel@...r.kernel.org>
Subject: Re: [PATCH] add b+tree library

On Sat, 10 January 2009 12:37:08 +0100, Johannes Berg wrote:
> On Sat, 2009-01-10 at 20:02 +0900, KOSAKI Motohiro wrote:
> 
> > > This adds a b+tree library. The API and memory layout is documented in
> > > the header file lib/btree.h. There are tree versions for 32, 64 and
> > > 128 bit keys as well as unsigned long (32/64 depending on platform).
> > 
> > Can this library remove the btree code in some btree based filesystem?
> 
> Joern is going to use it for logfs, that's the point. Not sure about
> other filesystems.

Err...

While true, this is decidedly _not_ a disk-based btree.  Logfs uses it
for in-memory data structures.  So the short answer is no.

There are several differences between this implementation and one used
for disk data.

- The value is a pointer, 32/64bit depending on architecture.  Won't be
  suited for a 64bit filesystem on a 32bit host, f.e.

- Lookups are a simple loop and don't use binary search.  With a 4KiB
  btree node and 64B cacheline, binary search will only load 7 out of 64
  cachelines - making a big difference.  This implementation uses 128B
  (or cacheline size, whichever is bigger) nodes, so binary search buy
  almost nothing, but cause branch mispredictions, bigger code, etc.

There may be more.  So if you plan to replace disk-based btree code with
this, it will certainly be some amount of work.  Not sure if it is a
good idea or if one should rather have a seperate library.

Jörn

-- 
The cost of changing business rules is much more expensive for software
than for a secretaty.
-- unknown
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/