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 <jc...@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
