[coreboot] [RFC]Hash based CMOS addressing scheme

[Patrick Georgi]

Hi,

been thinking about our use of CMOS for configuration lately, and
finally came up with a scheme that might just work out.

Currently, the CMOS layout is defined per-board making it cumbersome to
add new fields for chipset drivers (you have to update all boards that
use the component and CMOS, or suffer build errors).

So, my scheme works like this:
Define a family of up to 2^16 hash functions where each takes a string
and calculates a number between 128 and 1023. The functions can be
enumerated by a 16 bit number.

On build time, look for a hash function which calculates addresses from
each CMOS option name, so that the values do not overlap.
Store this number in the coreboot binary, and precalculate the addresses
of the options (they won't be neatly laid out as they tend to be now).

How does that help us?
First, we don't need to manually layout the CMOS memory space anymore,
which means, we can build partial cmos.layout files for components,
which are then concatenated.
This should help with CMOS adoption in drivers.

Second, updates become possible: If we store the number of the hash
function in CMOS (16 bit well spent - let's call it 'salt') at a well
known location, we can do in-place updates. We have to get through
romstage somehow (which we can ensure by extending the get_option API a
bit), at ramstage, coreboot can run an algorithm like:
 - check salt number in CMOS with salt number used in the build
 - if the same, check checksum, go on with boot.
 - if not the same:
   - for each cmos option do:
     - calculate the address with the old salt, read the value into RAM
   - for each cmos option do:
     - write to CMOS with the new addresses
       (as stored in coreboot binary or calculated with the new salt)
   - reboot (so romstage can pick up the CMOS values properly)

The hash function should be a "perfect hash" (akin to gperf), in that it
provides collision free values for a known set of inputs (where
"collision free" also includes address ranges, not just output numbers).
It can be computationally expensive at runtime, as it is not commonly
used - usually, the precomputed values in the binary can be used.
It can be computationally expensive at build time, as CMOS layout
doesn't change _that_ often (or we could use some form of caching)

The hard part will be to find such a hash function. The good thing is
that it doesn't have to be a cryptographically strong hash function, a
"normal" hash function is good enough.


Opinions?


Patrick