linux-kernel - Re: [RFC] B+Tree library V2

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: <20090108194031.GB24884@logfs.org>
Date:	Thu, 8 Jan 2009 20:40:32 +0100
From:	Jörn Engel <joern@...fs.org>
To:	Johannes Berg <johannes@...solutions.net>
Cc:	linux-kernel@...r.kernel.org
Subject: Re: [RFC] B+Tree library V2

On Thu, 8 January 2009 17:34:10 +0100, Johannes Berg wrote:
> 
> > Well, I used to have heaps of btrees around and wanted to share the
> > mempool between all of them.  Not sure if I still do, I believe not.
> > Will check.
> > 
> > If mempools aren't shared, I agree that encapsulating those bits is much
> > nicer.
> 
> Just made the API a bit quirky, maybe just support both ways of using
> things? Would only need a flag somewhere in the btree structure, I'd
> think; ultimately it doesn't matter much to me though.

I don't think we need a flag.  Just a regular pair of init/cleanup
functions and some __init_i_want_to_share_mempools_and_crawl_on_my_knees
without a cleanup for those who need it.

> > If you want to open-code it, you can use btree_lookup_less().  I added
> > that function sometime last month.  Basically something like this:
> > 	key = btree_last(head, geo);
> > 	while (key) {
> > 		/* do something with key */
> > 		key = btree_lookup_less(head, geo, key);
> > 	}
> > 
> > Maybe it should be renamed to btree_get_prev_key().  I never noticed how
> > confusing it was because my head was busy with other problems.  The code
> > is currently burried within my logfs tree:
> > http://logfs.org/git?p=logfs;a=summary
> 
> I don't think I've understood this yet. That code above there is a
> backwards walk over the key space, and it's safe to call
> btree_remove(key) at /* do something with key */?

Yes, it's a backwards walk.  The btree is sorted backwards as a
micro-optimization.  Loops will terminate a bit earlier without a
complicated test this way.

And you can do absolutely anything at  /* do something with key */.  The
btree_get_prev_key() will simply tell you what the next-lowest key in
the btree is at that time.  You no longer need locking around the whole
visitor, but can release the lock after each step, if you want.

Downside is that each step will walk the btree from the root again.
Twice, because you also need to lookup/remove each element.  Tanstaafl.

Jörn

-- 
Courage is not the absence of fear, but rather the judgement that
something else is more important than fear.
-- Ambrose Redmoon
--
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/