Re: db(3) removal and lastlogx

[David Laight <david%l8s.co.uk@localhost>]

On Thu, Jun 07, 2012 at 08:36:36AM +0200, Joerg Sonnenberger wrote:
> Hi all,
> there is a bit mechnical work left to remove db(3) dependencies e.g. for
> the password database, but that's mostly that. The last real consume of
> the db(3) API in libc is the lastlogx handling in utmpx. Basically, this
> logs a record in a file indexed by uid. I can think of three different
> approaches for dealing with this:
> 
> (1) Just use a sparse file. This requires by far the least amount of
> code, just some verification logic for a file header and writing to "uid
> * size of entry". Writes should be short enough to ensure atomic writes
> even on NFS. Same for reads. No manual locking needed.

Isn't that the 'traditional' format?
Presumably, at some point, that was replaced by the db format.
 
> (2) Implement a simple hierachical byte-level index, e.g. start by a
> table of 256 off_t entries, index with the LSB continue. For read
> hitting an off_t of 0 means the entry doesn't exist, for write get a
> byte range lock for that area, append a new index page / the entry to
> the file and use a single write to update it. Provide iterator interface
> to find all entries in the file. Somewhat more involved, but not too
> much.

A variant on that is to make the indexed 'off_t' either a pointer to
the actual data, or a pointer to the next level index block.
The data blocks need to contain their own value - and a check done.
(or put the number into the index array).
The lookup sequence is a simple loop - you don't need to know the
table level.
Works well provided the values are allocated in sequential blocks.
Inserts may need an index block created and its location written
into the file (overwriting the offset of an item), but otherwise 
the structure is static.

> (3) Implement on-disk PATRICA lookup. Still much simpler than b-tree,
> but also more work than (2).
> 
> Comments?
> 
> Joerg

        David

-- 
David Laight: david%l8s.co.uk@localhost