[Qemu-devel] [RFC PATCH 0/2] Auto-generated IDs

[Qemu-devel] [RFC PATCH 0/2] Auto-generated IDs

[Jeff Cody]

Born from the conversation on qemu-devel, this generation scheme uses the
format ultimately proposed by Kevin, after list discussion.

It attempts to keep the ID strings as small as possible, while fulfilling:
    
    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
        of object ordering and parsing (i.e., we don't want users to think
        they can guess the next ID based on prior behavior).

See patch 1 for the generation scheme details.

Jeff Cody (2):
  util - add automated ID generation utility
  block: auto-generated node-names

 block.c               | 25 ++++++++++++++++---------
 include/qemu-common.h |  8 ++++++++
 util/id.c             | 35 +++++++++++++++++++++++++++++++++++
 3 files changed, 59 insertions(+), 9 deletions(-)

-- 
1.9.3

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

[Jeff Cody]

Multiple sub-systems in QEMU may find it useful to generated 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 predictibility, 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 --|    |   | |
Subsytem String -----|   | |
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:

    #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             | 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",
+    };
+
+    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);
+}
-- 
1.9.3

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

[Eric Blake]

[-- Attachment #1: Type: text/plain, Size: 2327 bytes --]

On 09/01/2015 11:23 AM, Jeff Cody wrote:
> Multiple sub-systems in QEMU may find it useful to generated 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 predictibility, 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 --|    |   | |
> Subsytem String -----|   | |

s/Subsytem/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:

s/take the//

> 
>     #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             | 35 +++++++++++++++++++++++++++++++++++
>  2 files changed, 43 insertions(+)
> 

> +char *id_generate(IdSubSystems id)
> +{
> +    const char *id_subsys_str[] = {

s/id_/const id_/

> +        [ID_QDEV]  = "qdev",
> +        [ID_BLOCK] = "block",
> +    };

Do we want some sort of compile-time assertion that we have entries for
all id values?...

> +
> +    static uint64_t id_counters[ID_MAX];
> +    uint32_t rnd;
> +
> +    assert(id < ID_MAX);

...maybe in the form of assert(id_subsys_str[id])


> +
> +    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);
> +}
> 

Looks reasonable to me.

-- 
Eric Blake   eblake redhat com    +1-919-301-3266
Libvirt virtualization library http://libvirt.org


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 604 bytes --]

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

[Jeff Cody]

On Tue, Sep 01, 2015 at 12:55:15PM -0600, Eric Blake wrote:
> On 09/01/2015 11:23 AM, Jeff Cody wrote:
> > Multiple sub-systems in QEMU may find it useful to generated 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 predictibility, 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 --|    |   | |
> > Subsytem String -----|   | |
> 
> s/Subsytem/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:
> 
> s/take the//
> 
> > 
> >     #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             | 35 +++++++++++++++++++++++++++++++++++
> >  2 files changed, 43 insertions(+)
> > 
> 
> > +char *id_generate(IdSubSystems id)
> > +{
> > +    const char *id_subsys_str[] = {
> 
> s/id_/const id_/
> 

Good point.

> > +        [ID_QDEV]  = "qdev",
> > +        [ID_BLOCK] = "block",
> > +    };
> 
> Do we want some sort of compile-time assertion that we have entries for
> all id values?...
> 
> > +
> > +    static uint64_t id_counters[ID_MAX];
> > +    uint32_t rnd;
> > +
> > +    assert(id < ID_MAX);
> 
> ...maybe in the form of assert(id_subsys_str[id])
> 

Yes, I think we do.  If one is missing, that is certainly a mistake,
and we run the risk of collisions as well.

> 
> > +
> > +    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);
> > +}
> > 
> 
> Looks reasonable to me.
>

Thanks

-Jeff

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 <jcody@redhat.com>
> ---
>  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.

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

[Jeff Cody]

On Tue, Sep 01, 2015 at 03:13:52PM -0400, John Snow wrote:
> 
> 
> 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"
> 

All I can say is, sometimes my fingers don't obey my brain.


> >     #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             | 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.
> 

Possibly.  I'm neutral, we can move it out of the function and make it
static.

> > +    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.

Yes - that is actually what I meant to do.  We definitely want to 
enforce two digits for the random element.

Thanks,

Jeff

[Qemu-devel] [RFC PATCH 2/2] block: auto-generated node-names

[Jeff Cody]

If a node-name is not specified, automatically generate the node-name.

Generated node-names will use the "block" sub-system identifier.

Signed-off-by: Jeff Cody <jcody@redhat.com>
---
 block.c | 25 ++++++++++++++++---------
 1 file changed, 16 insertions(+), 9 deletions(-)

diff --git a/block.c b/block.c
index d088ee0..892e127 100644
--- a/block.c
+++ b/block.c
@@ -771,32 +771,39 @@ static void bdrv_assign_node_name(BlockDriverState *bs,
                                   const char *node_name,
                                   Error **errp)
 {
+    char *gen_node_name = NULL;
+
     if (!node_name) {
-        return;
-    }
-
-    /* Check for empty string or invalid characters */
-    if (!id_wellformed(node_name)) {
-        error_setg(errp, "Invalid node name");
-        return;
+        gen_node_name = id_generate(ID_BLOCK);
+        node_name = gen_node_name;
+    } else {
+        /* Check for empty string or invalid characters, but not if it is
+         * generated (generated names use characters not available to the user)
+         * */
+        if (!id_wellformed(node_name)) {
+            error_setg(errp, "Invalid node name");
+            return;
+        }
     }
 
     /* takes care of avoiding namespaces collisions */
     if (blk_by_name(node_name)) {
         error_setg(errp, "node-name=%s is conflicting with a device id",
                    node_name);
-        return;
+        goto out;
     }
 
     /* takes care of avoiding duplicates node names */
     if (bdrv_find_node(node_name)) {
         error_setg(errp, "Duplicate node name");
-        return;
+        goto out;
     }
 
     /* copy node name into the bs and insert it into the graph list */
     pstrcpy(bs->node_name, sizeof(bs->node_name), node_name);
     QTAILQ_INSERT_TAIL(&graph_bdrv_states, bs, node_list);
+out:
+    g_free(gen_node_name);
 }
 
 static QemuOptsList bdrv_runtime_opts = {
-- 
1.9.3

Re: [Qemu-devel] [RFC PATCH 2/2] block: auto-generated node-names

[Eric Blake]

[-- Attachment #1: Type: text/plain, Size: 500 bytes --]

On 09/01/2015 11:23 AM, Jeff Cody wrote:
> If a node-name is not specified, automatically generate the node-name.
> 
> Generated node-names will use the "block" sub-system identifier.
> 
> Signed-off-by: Jeff Cody <jcody@redhat.com>
> ---
>  block.c | 25 ++++++++++++++++---------
>  1 file changed, 16 insertions(+), 9 deletions(-)

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

-- 
Eric Blake   eblake redhat com    +1-919-301-3266
Libvirt virtualization library http://libvirt.org


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 604 bytes --]

Re: [Qemu-devel] [RFC PATCH 2/2] block: auto-generated node-names

[John Snow]

On 09/01/2015 01:23 PM, Jeff Cody wrote:
> If a node-name is not specified, automatically generate the node-name.
> 
> Generated node-names will use the "block" sub-system identifier.
> 
> Signed-off-by: Jeff Cody <jcody@redhat.com>
> ---
>  block.c | 25 ++++++++++++++++---------
>  1 file changed, 16 insertions(+), 9 deletions(-)
> 
> diff --git a/block.c b/block.c
> index d088ee0..892e127 100644
> --- a/block.c
> +++ b/block.c
> @@ -771,32 +771,39 @@ static void bdrv_assign_node_name(BlockDriverState *bs,
>                                    const char *node_name,
>                                    Error **errp)
>  {
> +    char *gen_node_name = NULL;
> +
>      if (!node_name) {
> -        return;
> -    }
> -
> -    /* Check for empty string or invalid characters */
> -    if (!id_wellformed(node_name)) {
> -        error_setg(errp, "Invalid node name");
> -        return;
> +        gen_node_name = id_generate(ID_BLOCK);
> +        node_name = gen_node_name;
> +    } else {
> +        /* Check for empty string or invalid characters, but not if it is
> +         * generated (generated names use characters not available to the user)
> +         * */
> +        if (!id_wellformed(node_name)) {
> +            error_setg(errp, "Invalid node name");
> +            return;
> +        }
>      }
>  
>      /* takes care of avoiding namespaces collisions */
>      if (blk_by_name(node_name)) {
>          error_setg(errp, "node-name=%s is conflicting with a device id",
>                     node_name);
> -        return;
> +        goto out;
>      }
>  
>      /* takes care of avoiding duplicates node names */
>      if (bdrv_find_node(node_name)) {
>          error_setg(errp, "Duplicate node name");
> -        return;
> +        goto out;
>      }
>  
>      /* copy node name into the bs and insert it into the graph list */
>      pstrcpy(bs->node_name, sizeof(bs->node_name), node_name);
>      QTAILQ_INSERT_TAIL(&graph_bdrv_states, bs, node_list);
> +out:
> +    g_free(gen_node_name);
>  }
>  
>  static QemuOptsList bdrv_runtime_opts = {
> 


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