Re: [Qemu-devel] [RFC PATCH 1/2] util - add automated ID generation utility

[John Snow]

On 09/01/2015 01:23 PM, Jeff Cody wrote:
> Multiple sub-systems in QEMU may find it useful to generated IDs

generate

> for objects that a user may reference via QMP or HMP.  This patch
> presents a standardized way to do it, so that automatic ID generation
> follows the same rules.
> 
> This patch enforces the following rules when generating an ID:
> 
> 1.) Guarantee no collisions with a user-specified ID
> 2.) Identify the sub-system the ID belongs to
> 3.) Guarantee of uniqueness
> 4.) Spoiling predictibility, to avoid creating an assumption

predictability

>     of object ordering and parsing (i.e., we don't want users to think
>     they can guess the next ID based on prior behavior).
> 
> The scheme for this is as follows (no spaces):
> 
>                 # subsys D RR
> Reserved char --|    |   | |
> Subsytem String -----|   | |

Subsystem

> Unique number (64-bit) --| |
> Two-digit random number ---|
> 
> For example, a generated node-name for the block sub-system may take the
> look like this:
> 

"take this form" or "look like this"

>     #block076
> 
> The caller of id_generate() is responsible for freeing the generated
> node name string with g_free().
> 
> Signed-off-by: Jeff Cody <address@hidden>
> ---
>  include/qemu-common.h |  8 ++++++++
>  util/id.c             | 35 +++++++++++++++++++++++++++++++++++
>  2 files changed, 43 insertions(+)
> 
> diff --git a/include/qemu-common.h b/include/qemu-common.h
> index bbaffd1..f6b0105 100644
> --- a/include/qemu-common.h
> +++ b/include/qemu-common.h
> @@ -237,6 +237,14 @@ int64_t strtosz_suffix_unit(const char *nptr, char **end,
>  #define STR_OR_NULL(str) ((str) ? (str) : "null")
>  
>  /* id.c */
> +
> +typedef enum IdSubSystems {
> +    ID_QDEV,
> +    ID_BLOCK,
> +    ID_MAX      /* last element, used as array size */
> +} IdSubSystems;
> +
> +char *id_generate(IdSubSystems);
>  bool id_wellformed(const char *id);
>  
>  /* path.c */
> diff --git a/util/id.c b/util/id.c
> index 09b22fb..48e2935 100644
> --- a/util/id.c
> +++ b/util/id.c
> @@ -26,3 +26,38 @@ bool id_wellformed(const char *id)
>      }
>      return true;
>  }
> +
> +#define ID_SPECIAL_CHAR '#'
> +
> +/* Generates an ID of the form:
> + *
> + * "#block146",
> + *
> + *  where:
> + *      - "#" is always the reserved character '#'
> + *      - "block" refers to the subsystem identifed via IdSubSystems
> + *        and id_subsys_str[]
> + *      - "1" is a unique number (up to a uint64_t) for the subsystem,
> + *      - "46" is a pseudo-random numer to create uniqueness
> + *
> + * The caller is responsible for freeing the returned string with g_free()
> + */
> +char *id_generate(IdSubSystems id)
> +{
> +    const char *id_subsys_str[] = {
> +        [ID_QDEV]  = "qdev",
> +        [ID_BLOCK] = "block",
> +    };
> +

Do we want this local to this function? A lookup table may be useful for
utilities at some point.

> +    static uint64_t id_counters[ID_MAX];
> +    uint32_t rnd;
> +
> +    assert(id < ID_MAX);
> +
> +    rnd = g_random_int_range(0, 99);
> +
> +    return g_strdup_printf("%c%s%" PRIu64 "%" PRId32, ID_SPECIAL_CHAR,
> +                                                      id_subsys_str[id],
> +                                                      id_counters[id]++,
> +                                                      rnd);
> +}
> 

So basically, it's #<sys><counter><rnd>

So we could see:

|block|1|32|

For the block subsystem, 1st device, salt is 3.
But we could also see:

|block|13|2|

Block subsys, 13th device, salt is 2.

Forcing a zero-pad on the salt should be enough to disambiguate in all
cases:

block132
block1302

This way, the last two digits are *always* salt, making the ID
unambiguous and, I think, impossible to collide against regardless of
that the rng returns in the future for new IDs.