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