[lkml]   [2012]   [Mar]   [1]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
SubjectRE: RFC: memory leak in udp_table_init

> > The pid table is a good example of something where a hash
> > table is unnecessary.
> > Linux should steal the code I put into NetBSD :-)
> On this unrelated topic. What algorithm did you use on NetBSD for
> dealing with pids?

Basically I forced the hash chain length to one by allocating
a pid that hit an empty entry in the table.

So you start off with (say) 64 entries and use the low 6
bits to index the table. The higher bits are incremented
each time a 'slot' is reused.
Free entries are kept in a FIFO list.
So each entry either contains a pointer to the process,
or the high bits and the index of the next free slot.
(and the PGID pointer).
When there are only (say) 2 free entries, then the table
size is doubled, the pointers moved to the correct places,
the free ist fixed up, and the minimum number of free entries

The overall effect:
- lookup is only ever a mask and index + compare.
- Allocate is always fast and fixed cost (except when
the table size has to be doubled).
- A pid value will never be reused within (about) 2000
allocates (for 16bit pids, much larger for 32bit ones).
- Allocated pid numbers tend to be random, certainly
very difficult to predict.
- Small memory footprint for small systems.
For pids we normally avoid issuing large values, but
will do so to avoid immediate re-use on systems that
have 1000s of active processes.

See lines 580-820 of


 \ /
  Last update: 2012-03-01 09:57    [from the cache]
©2003-2014 Jasper Spaans. hosted at Digital Ocean