[v2,1/2] util - add automated ID generation utility

Multiple sub-systems in QEMU may find it useful to generate IDs
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 predictability, to avoid creating an assumption
    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 --|    |   | |
Subsystem String ----|   | |
Unique number (64-bit) --| |
Two-digit random number ---|

For example, a generated node-name for the block sub-system may 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 <jcody@redhat.com>
---
 include/qemu-common.h |  8 ++++++++
 util/id.c             | 36 ++++++++++++++++++++++++++++++++++++
 2 files changed, 44 insertions(+)

On 09/01/2015 04:30 PM, Jeff Cody wrote:
> Multiple sub-systems in QEMU may find it useful to generate IDs
> 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 predictability, to avoid creating an assumption
>     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 --|    |   | |
> Subsystem String ----|   | |
> Unique number (64-bit) --| |
> Two-digit random number ---|
> 
> For example, a generated node-name for the block sub-system may 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 <jcody@redhat.com>
> ---
>  include/qemu-common.h |  8 ++++++++
>  util/id.c             | 36 ++++++++++++++++++++++++++++++++++++
>  2 files changed, 44 insertions(+)

Reviewed-by: Eric Blake <eblake@redhat.com>

> +
> +static const char * const id_subsys_str[] = {
> +    [ID_QDEV]  = "qdev",
> +    [ID_BLOCK] = "block",
> +};

We're inconsistent on whether there should be a space in '*const'
(compare commit a91e211 with b86f461, for example).  But since qemu.git
has both spellings in various contexts, it's probably not worth changing
here.

> +
> +    rnd = g_random_int_range(0, 99);

Thankfully, g_random_* is a PRNG that is not consuming system entropy
(auto-generated names should not be starving /dev/random).

On Tue, Sep 01, 2015 at 04:55:16PM -0600, Eric Blake wrote:
> On 09/01/2015 04:30 PM, Jeff Cody wrote:
> > Multiple sub-systems in QEMU may find it useful to generate IDs
> > 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 predictability, to avoid creating an assumption
> >     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 --|    |   | |
> > Subsystem String ----|   | |
> > Unique number (64-bit) --| |
> > Two-digit random number ---|
> > 
> > For example, a generated node-name for the block sub-system may 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 <jcody@redhat.com>
> > ---
> >  include/qemu-common.h |  8 ++++++++
> >  util/id.c             | 36 ++++++++++++++++++++++++++++++++++++
> >  2 files changed, 44 insertions(+)
> 
> Reviewed-by: Eric Blake <eblake@redhat.com>
> 
> > +
> > +static const char * const id_subsys_str[] = {
> > +    [ID_QDEV]  = "qdev",
> > +    [ID_BLOCK] = "block",
> > +};
> 
> We're inconsistent on whether there should be a space in '*const'
> (compare commit a91e211 with b86f461, for example).  But since qemu.git
> has both spellings in various contexts, it's probably not worth changing
> here.
> 

If this ends up needing another rev, I'll change it for you :)

> > +
> > +    rnd = g_random_int_range(0, 99);
> 
> Thankfully, g_random_* is a PRNG that is not consuming system entropy
> (auto-generated names should not be starving /dev/random).
>

Yup.


Thanks,

Jeff

On 09/01/2015 06:30 PM, Jeff Cody wrote:
> Multiple sub-systems in QEMU may find it useful to generate IDs
> 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 predictability, to avoid creating an assumption
>     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 --|    |   | |
> Subsystem String ----|   | |
> Unique number (64-bit) --| |
> Two-digit random number ---|
> 
> For example, a generated node-name for the block sub-system may 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 <jcody@redhat.com>
> ---
>  include/qemu-common.h |  8 ++++++++
>  util/id.c             | 36 ++++++++++++++++++++++++++++++++++++
>  2 files changed, 44 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..9457f2d 100644
> --- a/util/id.c
> +++ b/util/id.c
> @@ -26,3 +26,39 @@ bool id_wellformed(const char *id)
>      }
>      return true;
>  }
> +
> +#define ID_SPECIAL_CHAR '#'
> +
> +static const char * const id_subsys_str[] = {
> +    [ID_QDEV]  = "qdev",
> +    [ID_BLOCK] = "block",
> +};
> +
> +/* 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 zero-padded two digit pseudo-random number
> + *
> + * The caller is responsible for freeing the returned string with g_free()
> + */
> +char *id_generate(IdSubSystems id)
> +{
> +    static uint64_t id_counters[ID_MAX];
> +    uint32_t rnd;
> +
> +    assert(id < ID_MAX);
> +    assert(id_subsys_str[id]);
> +
> +    rnd = g_random_int_range(0, 99);
> +
> +    return g_strdup_printf("%c%s%" PRIu64 "%02" PRId32, ID_SPECIAL_CHAR,
> +                                                        id_subsys_str[id],
> +                                                        id_counters[id]++,
> +                                                        rnd);
> +}
> 

Seems good to me.

Reviewed-by: John Snow <jsnow@redhat.com>

On Wed 02 Sep 2015 12:30:15 AM CEST, Jeff Cody <jcody@redhat.com> wrote:

> Multiple sub-systems in QEMU may find it useful to generate IDs
> 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.

> +
> +typedef enum IdSubSystems {
> +    ID_QDEV,
> +    ID_BLOCK,
> +    ID_MAX      /* last element, used as array size */
> +} IdSubSystems;
> +
> +char *id_generate(IdSubSystems);

Not that it matters much, but it seems that everywhere else in the QEMU
source code the rule is to name the parameters in function prototypes.

Otherwise, the patch looks good!

Reviewed-by: Alberto Garcia <berto@igalia.com>

Berto

On Wed, Sep 02, 2015 at 08:35:37AM +0200, Alberto Garcia wrote:
> On Wed 02 Sep 2015 12:30:15 AM CEST, Jeff Cody <jcody@redhat.com> wrote:
> 
> > Multiple sub-systems in QEMU may find it useful to generate IDs
> > 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.
> 
> > +
> > +typedef enum IdSubSystems {
> > +    ID_QDEV,
> > +    ID_BLOCK,
> > +    ID_MAX      /* last element, used as array size */
> > +} IdSubSystems;
> > +
> > +char *id_generate(IdSubSystems);
> 
> Not that it matters much, but it seems that everywhere else in the QEMU
> source code the rule is to name the parameters in function prototypes.
>

Indeed... another syntactic tweak to make if a v3 is needed (or a
maintainer insists!)

> Otherwise, the patch looks good!
> 
> Reviewed-by: Alberto Garcia <berto@igalia.com>
> 
> Berto

Thanks!

-Jeff

Jeff Cody <jcody@redhat.com> writes:

> Multiple sub-systems in QEMU may find it useful to generate IDs
> 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 predictability, to avoid creating an assumption
>     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 --|    |   | |
> Subsystem String ----|   | |
> Unique number (64-bit) --| |
> Two-digit random number ---|
>
> For example, a generated node-name for the block sub-system may 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 <jcody@redhat.com>
> ---
>  include/qemu-common.h |  8 ++++++++
>  util/id.c             | 36 ++++++++++++++++++++++++++++++++++++
>  2 files changed, 44 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..9457f2d 100644
> --- a/util/id.c
> +++ b/util/id.c
> @@ -26,3 +26,39 @@ bool id_wellformed(const char *id)
>      }
>      return true;
>  }
> +
> +#define ID_SPECIAL_CHAR '#'
> +
> +static const char * const id_subsys_str[] = {

Like Eric, I'd prefer *const.

> +    [ID_QDEV]  = "qdev",
> +    [ID_BLOCK] = "block",
> +};
> +
> +/* Generates an ID of the form:

Style nit: wing you comments on both ends, please.

> + *
> + * "#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 zero-padded two digit pseudo-random number

Recommend to note that the value does not satisfy id_wellformed().

I'd specify a bit more losely:

/*
 * Generates an ID of the form PREFIX SUBSYSTEM NUMBER
 * where
 * - PREFIX is the reserved character '#'
 * - SUBSYSTEM identifies the subsystem creating the ID
 * - NUMBER is a decimal number unique within SUBSYSTEM.
 * Example: "#block146"
 *
 * Note that these IDs do not satisfy id_wellformed().

> + *
> + * The caller is responsible for freeing the returned string with g_free()
> + */
> +char *id_generate(IdSubSystems id)
> +{
> +    static uint64_t id_counters[ID_MAX];
> +    uint32_t rnd;
> +
> +    assert(id < ID_MAX);
> +    assert(id_subsys_str[id]);
> +
> +    rnd = g_random_int_range(0, 99);

99 is off by one: "Returns a random gint32 equally distributed over the
range [begin ..end -1]."

> +
> +    return g_strdup_printf("%c%s%" PRIu64 "%02" PRId32, ID_SPECIAL_CHAR,
> +                                                        id_subsys_str[id],
> +                                                        id_counters[id]++,
> +                                                        rnd);
> +}