Auto-generated IDs

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 <[email protected]>

---
 include/qemu-common.h |  8 ++++++++
 util/id.c             | 35 +++++++++++++++++++++++++++++++++++
 2 files changed, 43 insertions(+)

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 <[email protected]>

---
 block.c | 25 ++++++++++++++++---------
 1 file changed, 16 insertions(+), 9 deletions(-)

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 <[email protected]>

---
 include/qemu-common.h |  8 ++++++++
 util/id.c             | 35 +++++++++++++++++++++++++++++++++++
 2 files changed, 43 insertions(+)

include/qemu-common.h +8 -0

index bbaffd1..f6b0105 100644
@@ -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 */

util/id.c +13 -0

index 09b22fb..48e2935 100644
@@ -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

Quoted 14 lines · 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).

Quoted 5 lines

The scheme for this is as follows (no spaces):

                # subsys D RR
Reserved char --|    |   | |
Subsytem String -----|   | |

s/Subsytem/Subsystem/

Quoted 5 lines

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//

Quoted 12 lines

    #block076

The caller of id_generate() is responsible for freeing the generated node name string with g_free().

Signed-off-by Jeff Cody <[email protected]>

---
 include/qemu-common.h |  8 ++++++++
 util/id.c             | 35 +++++++++++++++++++++++++++++++++++
 2 files changed, 43 insertions(+)

util/id.c bool id_wellformed(const char *id) · line 47

Quoted 3 lines

util/id.c +3 -0

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

s/id_/const id_/

util/id.c bool id_wellformed(const char *id) · line 50

Quoted 3 lines

util/id.c +3 -0

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

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

util/id.c bool id_wellformed(const char *id) · line 55

Quoted 5 lines

util/id.c +5 -0

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

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

util/id.c bool id_wellformed(const char *id) · line 63

Quoted 10 lines

util/id.c +8 -0

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

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 <[email protected]>

---
 block.c | 25 ++++++++++++++++---------
 1 file changed, 16 insertions(+), 9 deletions(-)

block.c +14 -9

index d088ee0..892e127 100644
@@ -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;

Quoted 1 line · Jeff Cody

Multiple sub-systems in QEMU may find it useful to generated IDs

generate

Quoted 10 lines

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

Quoted 8 lines

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

Quoted 6 lines

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"

Quoted 56 lines

    #block076

The caller of id_generate() is responsible for freeing the generated node name string with g_free().

Signed-off-by Jeff Cody <[email protected]>

---
 include/qemu-common.h |  8 ++++++++
 util/id.c             | 35 +++++++++++++++++++++++++++++++++++
 2 files changed, 43 insertions(+)

include/qemu-common.h +8 -0

index bbaffd1..f6b0105 100644
@@ -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 */

util/id.c +18 -0

index 09b22fb..48e2935 100644
@@ -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)
+{

util/id.c bool id_wellformed(const char *id) · line 51

Quoted 5 lines

util/id.c +5 -0

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

util/id.c bool id_wellformed(const char *id) · line 63

Quoted 13 lines

util/id.c +12 -0

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