[PATCH] tdb: recycle dead records always at chain top

[Michael Adam]

On 2014-04-02 at 11:28 -0700, Jeremy Allison wrote:
> On Tue, Apr 01, 2014 at 01:49:45PM +0200, Michael Adam wrote:
> > Hi,
> > 
> > based on Volker's patches from a couple of days ago,
> > here is a patch that simplifies the code a bit
> > (removes an almost-duplication). It changes the
> > semantics in that when recycling a record from the
> > chain to which the record-to-be-stored belongs,
> > we do not leave it in place and more but put it
> > to the top of the chain too (as with freelist records
> > and records recycled from other chains).
> > 
> > This may give an advantage when trying to find the record
> > again soon, but a disadvantage are the two
> > additional tdb_ofs_write calls.
> > 
> > Thoughts?
> 
> I have gone over this code really carefully :-).
> 
> Thanks.
> 
> The only change I'd make is to split out this
> change:
> 
> > diff --git a/lib/tdb/common/freelist.c b/lib/tdb/common/freelist.c
> > index 6f8f812..2aeeb1c 100644
> > --- a/lib/tdb/common/freelist.c
> > +++ b/lib/tdb/common/freelist.c
> > @@ -404,22 +404,10 @@ tdb_off_t tdb_allocate(struct tdb_context *tdb, int hash, tdb_len_t length,
> >  	 * hash chains, something which is pretty bad normally)
> >  	 */
> >  
> > -	for (i=1; i<tdb->hash_size; i++) {
> > +	for (i=0; i<tdb->hash_size; i++) {
> 
> The change from starting from i=1, to i=0
> needs a separate explaination. I (think :-)
> I understand it, but as it's a change in
> code behavior I'd like to see it as a
> separate commit with an explaination
> of why it was done.

Hmmm, I don't quite see that this can be split out.
This is quite naturally part of the change. Let me
explain:

If we extract the essence of the code from _tdb_store and
tdb_allocate, the flow currently is this:

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
	if (!dead records enabled) {
		goto blocking_freelist_alloc
	}

	find dead in current chain
	if (found) {
		recycle record in place (filling key and data)
		goto done
	}

	for (i=1; i<hash_size; i++) {
		try non-blocking allocation from freelist
		if (success) {
			goto recycle_unliked_record
		}

		find dead in current chain + i
		if (found) {
			unlink from chain
			goto recycle_unliked_record
		}
	}

blocking_freelist_alloc:
	do blocking allocation from freelist

recycle_unliked_record:
	fill record with key and data
	prepend record to current chain

done:
	done
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

After my change it reads:

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
	if (!dead records enabled) {
		goto blocking_freelist_alloc
	}

	for (i=0; i<hash_size; i++) {
		find dead in current chain + i
		if (found) {
			unlink from chain
			goto recycle_unliked_record
		}

		try non-blocking allocation from freelist
		if (success) {
			goto recycle_unliked_record
		}
	}

blocking_freelist_alloc:
	do blocking allocation from freelist

recycle_unlinked_record:
	fill record with data and key
	prepend record to current chain

done:
	done
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

I.e. the subtelty is that before my change, the i = 0 case, which
is the case of the current candidate record's chain, is a special
case treated outside of the for loop.

My change removes the special treatment of this
case, and hence moves this into the loop, but reverses
the order of the two steps inside of the loop, so that
the order of execution remains the same as before.

So I don't quite see how I can untangle this reasonably
into multiple commits. (You know I am in favour of many
small commits...) Each such commit I can imagine, would
create a bigger change in behaviour.

If you can give me a hint, I will gladly follow up with
an updated patch(set), but maybe the change just needs
a better commit message.

> Other than that +1 from me - nice cleanup !

Thanks! - Michael
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 215 bytes
Desc: Digital signature
URL: <http://lists.samba.org/pipermail/samba-technical/attachments/20140409/0a77cdd6/attachment.pgp>