[patch] UBIFS: add key state map data structure and accessors

[Artem Bityutskiy]

On Sat, 2012-06-09 at 00:16 +0200, Joel Reardon wrote:
> #define KEYMAP_STATES_PER_BYTE_SHIFT 2
> +
> +/**
> + * Defines the three possible states of a key:
> + * @KEYMAP_STATE_UNUSED: the key has never been assigned or used
> + * @KEYMAP_STATE_USED: the key has been assigned and is used for live data
> + * @KEYMAP_STATE_DELETED: the key has been assigned and is used for
> + *			  deleted data.
> + */
> +enum {
> +	KEYMAP_STATE_UNUSED  = 0,
> +	KEYMAP_STATE_USED    = 1,
> +	KEYMAP_STATE_DELETED = 2,

I'd suggest to remove the values, they are the same as the  default
ones, and add
          KEYMAP_STATE_CNT,

to have the count of states for ubifs_assert() below.

> +};
> +
>  /**
>   * struct ubifs_keymap - UBIFS key map.
>   * @key_size: size of a key in bytes
>   * @keys_per_leb: number of keys per KSA LEB
> - * @ksa_size: number of LEBS in the KSA
> + * @ksa_lebs: number of LEBS in the KSA
>   * @ksa_first: the first LEB belonging to the KSA

Yo do not have "ksa_first".

> + * @state: a double-array [ksa_lebs]x[keys_per_leb] that stores the
> + *	   state of the key at that position. The state consumes two bits so
> + *	   each byte contains four states. The first index is from 0 to the
> + *	   number of KSA LEBs - 1, and the second is from 0 to the number of
> + *	   keys per (KSA LEB - 1) >> 2

I do not understand this "number of  keys per (KSA LEB - 1) >> 2" - it
should be "number of keys per KSA LEB", no?

> +static void set_state(struct ubifs_keymap *km, int ksa_leb,
> +		      int ksa_offset, int value)
> +{
> +	static const int minor_mask = (1 << KEYMAP_STATES_PER_BYTE_SHIFT) - 1;
> +	int major, shift, mask, old;
> +

ubifs_assert(ksa_leb is sane);
ubifs_assert(value > 0 && value < KEYMAP_STATE_CNT);
ubifs_assert(ksa_offset > 0 && ksa_offset <= c->leb_size - UBIFS_CRYPTO_KEYSIZE);

unless this is fast-path where we'd want to avoid wasting time for checks,
but it does not look so.

> +	major = ksa_offset >> KEYMAP_STATES_PER_BYTE_SHIFT;
> +	shift = (ksa_offset & minor_mask) << 1;
> +	mask  = minor_mask << shift;
> +	old = km->state[ksa_leb][major];
> +	km->state[ksa_leb][major] = old - (old & mask) + (value << shift);
> +}

All you need to do is to set the stat in the array of bits, right?
Wouldn't something straightforward like this be simpler?

uint8_t *byte = km->start[ksa_leb][ksa_offset / UBIFS_CRYPTO_KEYSIZE];
pair = ksa_offset % 4;
*byte &= value << pair * 2;

Frankly, I cannot parse your implementation, but I did not try too hard.

Btw, do not try too hare do use shifts instead of multiplications,
modern compilers and processors are smart enough to do it themselves.

> +
> +/**
> + * get_state - get the key state
> + * @km: the keymap
> + * @ksa_leb: the KSA eraseblock number
> + * @ksa_offset: the key's offset in the KSA eraseblock
> + *
> + * This function returns key position's state.
> + */
> +static int get_state(struct ubifs_keymap *km, int ksa_leb, int ksa_offset)
> +{
> +	static const int minor_mask = (1 << KEYMAP_STATES_PER_BYTE_SHIFT) - 1;
> +	int major, shift;
> +
> +	major = ksa_offset >> KEYMAP_STATES_PER_BYTE_SHIFT;
> +	shift = (ksa_offset & minor_mask) << 1;
> +	return (km->state[ksa_leb][major] >> shift) & minor_mask;
> +}

Similarly, add assertion to check that you never return 0x3. Check input
parameters. Would this be simpler to understand?

byte = km->start[ksa_leb][ksa_offset / UBIFS_CRYPTO_KEYSIZE];
pair = ksa_offset % 4;
ret = byte >> pair * 2;

-- 
Best Regards,
Artem Bityutskiy
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 836 bytes
Desc: This is a digitally signed message part
URL: <http://lists.infradead.org/pipermail/linux-mtd/attachments/20120618/e0f31b9b/attachment.sig>