[syslinux] Cascading LRU

[H. Peter Anvin]

This comes from a discussion on IRC about how to handle multiple block
sizes.

One option is "one cache per block size".  A more efficient, but more
complex, variant looks like this:

For each block size supported, we pair things into a set of cascading
sizes.  For the purpose of this post, the sizes are 512-4096 bytes, but
the extrapolation to bigger sizes should be obvious.

Consider the blocks split as follows (using a 8K cache as an example):

512 B		1K		2K		4K

A	\
	 >	AB	\
B	/		 \
			  >	AD	\
C	\		 /		 \
	 >	CD	/		  \
D	/				   \
					    >	AH
E	\				   /
	 >	EF	\		  /
F	/		 \		 /
			  >	EH	/
G	\		 /
	 >	GH	/
H	/

I	\
	 >	IJ	\
J	/		 \
			  >	IL	\
K	\		 /		 \
	 >	KL	/		  \
L	/				   \
					    >	IP
M	\				   /
	 >	MN	\		  /
N	/		 \		 /
			  >	MP	/
O	\		 /
	 >	OP	/
P	/



Consider a counter for each 512-byte block.  When a block is accessed,
all the counters for each touched 512-byte block are updated (so if
block IL is touched, counters I, J, K and L are updated.)  When we look
for space for a block, look at each set of counters and find the maximum
of each, and then take the minimum.   Again, for a 2K block, we would
look at each group A-D, E-H, I-L, M-P, take the maximum inside each
group, and then find the group with the minimum.  Those blocks can be
invalidated and replaced with the new block.

As described, this is an O(n) implementation.  LRU using a doubly-linked
list is O(1); it is unclear to me if that matters for Syslinux, but if
it does I think we can make it happen via some kind of sane data structure.

	-hpa