| Message ID | 1362520494-8917-3-git-send-email-matt@console-pimps.org |
|---|---|
| State | Accepted |
| Headers | show |
On 05/03/13 21:54, Matt Fleming wrote: > From: Matt Fleming <matt.fleming@intel.com> > > There have been reports that some implementations of > GetNextVariableName() return duplicate variables, > > https://bugzilla.kernel.org/show_bug.cgi?id=47631 > > Use a simple hash bucket algorithm to check the uniqueness of each > variable and error if we encounter any duplicates. > > Signed-off-by: Matt Fleming <matt.fleming@intel.com> > --- > src/uefi/uefirtvariable/uefirtvariable.c | 155 +++++++++++++++++++++++++++++++ > 1 file changed, 155 insertions(+) > > diff --git a/src/uefi/uefirtvariable/uefirtvariable.c b/src/uefi/uefirtvariable/uefirtvariable.c > index 177dbf9..fe4cdce 100644 > --- a/src/uefi/uefirtvariable/uefirtvariable.c > +++ b/src/uefi/uefirtvariable/uefirtvariable.c > @@ -401,7 +401,158 @@ static int getnextvariable_test2(fwts_framework *fw) > return FWTS_OK; > > err: > + return FWTS_ERROR; > +} > + > +struct efi_var_item { > + struct efi_var_item *next; /* collision chain */ > + uint16_t *name; > + EFI_GUID *guid; > + uint64_t hash; > +}; > + > +/* > + * This is a completely arbitrary value. > + */ > +#define BUCKET_SIZE 32 > +static struct efi_var_item *buckets[BUCKET_SIZE]; > + > +/* > + * This doesn't have to be a super efficient hashing function with > + * minimal collisions, just more efficient than iterating over a > + * simple linked list. > + */ > +static inline uint64_t hash_func(uint16_t *variablename, uint64_t length) > +{ > + uint64_t i, hash = 0; > + uint16_t *c = variablename; > + > + for (i = 0; i < length; i++) > + hash = hash * 33 + *c++; > + > + return hash; > +} > + > +/* > + * Return's 0 on success, -1 if there was a collision - meaning we've > + * encountered duplicate variable names with the same GUID. > + */ > +static int bucket_insert(struct efi_var_item *item) > +{ > + struct efi_var_item *chain; > + unsigned int index = item->hash % BUCKET_SIZE; > + > + chain = buckets[index]; > + > + while (chain) { > + /* > + * OK, we got a collision - no big deal. Walk the > + * chain and see whether this variable name and > + * variable guid already appear on it. > + */ > + if (compare_name(item->name, chain->name)) { > + if (compare_guid(item->guid, chain->guid)) > + return -1; /* duplicate */ > + } > + > + chain = chain->next; > + } > + > + item->next = buckets[index]; > + buckets[index] = item; > + return 0; > +} > + > +static void bucket_destroy(void) > +{ > + struct efi_var_item *item; > + int i; > + > + for (i = 0; i < BUCKET_SIZE; i++) { > + item = buckets[i]; > + > + while (item) { > + struct efi_var_item *chain = item->next; > + > + free(item->name); > + free(item); > + item = chain; > + } > + } > +} > + > +static int getnextvariable_test3(fwts_framework *fw) > +{ > + long ioret; > + uint64_t status; > > + struct efi_getnextvariablename getnextvariablename; > + uint64_t variablenamesize = MAX_DATA_LENGTH; > + uint16_t variablename[MAX_DATA_LENGTH]; > + EFI_GUID vendorguid; > + > + getnextvariablename.VariableNameSize = &variablenamesize; > + getnextvariablename.VariableName = variablename; > + getnextvariablename.VendorGuid = &vendorguid; > + getnextvariablename.status = &status; > + > + /* To start the search, need to pass a Null-terminated string in VariableName */ > + variablename[0] = '\0'; > + while (true) { > + struct efi_var_item *item; > + > + variablenamesize = MAX_DATA_LENGTH; > + ioret = ioctl(fd, EFI_RUNTIME_GET_NEXTVARIABLENAME, &getnextvariablename); > + > + if (ioret == -1) { > + > + /* no next variable was found*/ > + if (*getnextvariablename.status == EFI_NOT_FOUND) > + break; > + > + fwts_failed(fw, LOG_LEVEL_HIGH, "UEFIRuntimeGetNextVariableName", > + "Failed to get next variable name with UEFI runtime service."); > + fwts_uefi_print_status_info(fw, status); > + goto err; > + } > + > + item = malloc(sizeof(*item)); > + if (!item) { > + fwts_failed(fw, LOG_LEVEL_HIGH, "UEFIRuntimeGetNextVariableName", > + "Failed to allocate memory for test."); > + goto err; > + } > + > + item->guid = &vendorguid; > + item->next = NULL; > + > + item->name = malloc(variablenamesize); > + if (!item->name) { > + fwts_failed(fw, LOG_LEVEL_HIGH, "UEFIRuntimeGetNextVariableName", > + "Failed to allocate memory for test."); > + free(item); > + goto err; > + } > + > + memcpy(item->name, variablename, variablenamesize); > + > + /* Ensure there are no duplicate variable names + guid */ > + item->hash = hash_func(variablename, variablenamesize); > + > + if (bucket_insert(item)) { > + fwts_failed(fw, LOG_LEVEL_HIGH, "UEFIRuntimeGetNextVariableName", > + "Duplicate variable name found."); > + free(item->name); > + free(item); > + goto err; > + } > + }; > + > + bucket_destroy(); > + return FWTS_OK; > + > +err: > + bucket_destroy(); > return FWTS_ERROR; > } > > @@ -931,6 +1082,10 @@ static int uefirtvariable_test2(fwts_framework *fw) > if (ret != FWTS_OK) > return ret; > > + ret = getnextvariable_test3(fw); > + if (ret != FWTS_OK) > + return ret; > + > fwts_passed(fw, "UEFI runtime service GetNextVariableName interface test passed."); > > return FWTS_OK; > Acked-by: Colin Ian King <colin.king@canonical.com>
On 03/06/2013 05:54 AM, Matt Fleming wrote: > From: Matt Fleming <matt.fleming@intel.com> > > There have been reports that some implementations of > GetNextVariableName() return duplicate variables, > > https://bugzilla.kernel.org/show_bug.cgi?id=47631 > > Use a simple hash bucket algorithm to check the uniqueness of each > variable and error if we encounter any duplicates. > > Signed-off-by: Matt Fleming <matt.fleming@intel.com> > --- > src/uefi/uefirtvariable/uefirtvariable.c | 155 +++++++++++++++++++++++++++++++ > 1 file changed, 155 insertions(+) > > diff --git a/src/uefi/uefirtvariable/uefirtvariable.c b/src/uefi/uefirtvariable/uefirtvariable.c > index 177dbf9..fe4cdce 100644 > --- a/src/uefi/uefirtvariable/uefirtvariable.c > +++ b/src/uefi/uefirtvariable/uefirtvariable.c > @@ -401,7 +401,158 @@ static int getnextvariable_test2(fwts_framework *fw) > return FWTS_OK; > > err: > + return FWTS_ERROR; > +} > + > +struct efi_var_item { > + struct efi_var_item *next; /* collision chain */ > + uint16_t *name; > + EFI_GUID *guid; > + uint64_t hash; > +}; > + > +/* > + * This is a completely arbitrary value. > + */ > +#define BUCKET_SIZE 32 > +static struct efi_var_item *buckets[BUCKET_SIZE]; > + > +/* > + * This doesn't have to be a super efficient hashing function with > + * minimal collisions, just more efficient than iterating over a > + * simple linked list. > + */ > +static inline uint64_t hash_func(uint16_t *variablename, uint64_t length) > +{ > + uint64_t i, hash = 0; > + uint16_t *c = variablename; > + > + for (i = 0; i < length; i++) > + hash = hash * 33 + *c++; > + > + return hash; > +} > + > +/* > + * Return's 0 on success, -1 if there was a collision - meaning we've > + * encountered duplicate variable names with the same GUID. > + */ > +static int bucket_insert(struct efi_var_item *item) > +{ > + struct efi_var_item *chain; > + unsigned int index = item->hash % BUCKET_SIZE; > + > + chain = buckets[index]; > + > + while (chain) { > + /* > + * OK, we got a collision - no big deal. Walk the > + * chain and see whether this variable name and > + * variable guid already appear on it. > + */ > + if (compare_name(item->name, chain->name)) { > + if (compare_guid(item->guid, chain->guid)) > + return -1; /* duplicate */ > + } > + > + chain = chain->next; > + } > + > + item->next = buckets[index]; > + buckets[index] = item; > + return 0; > +} > + > +static void bucket_destroy(void) > +{ > + struct efi_var_item *item; > + int i; > + > + for (i = 0; i < BUCKET_SIZE; i++) { > + item = buckets[i]; > + > + while (item) { > + struct efi_var_item *chain = item->next; > + > + free(item->name); > + free(item); > + item = chain; > + } > + } > +} > + > +static int getnextvariable_test3(fwts_framework *fw) > +{ > + long ioret; > + uint64_t status; > > + struct efi_getnextvariablename getnextvariablename; > + uint64_t variablenamesize = MAX_DATA_LENGTH; > + uint16_t variablename[MAX_DATA_LENGTH]; > + EFI_GUID vendorguid; > + > + getnextvariablename.VariableNameSize = &variablenamesize; > + getnextvariablename.VariableName = variablename; > + getnextvariablename.VendorGuid = &vendorguid; > + getnextvariablename.status = &status; > + > + /* To start the search, need to pass a Null-terminated string in VariableName */ > + variablename[0] = '\0'; > + while (true) { > + struct efi_var_item *item; > + > + variablenamesize = MAX_DATA_LENGTH; > + ioret = ioctl(fd, EFI_RUNTIME_GET_NEXTVARIABLENAME, &getnextvariablename); > + > + if (ioret == -1) { > + > + /* no next variable was found*/ > + if (*getnextvariablename.status == EFI_NOT_FOUND) > + break; > + > + fwts_failed(fw, LOG_LEVEL_HIGH, "UEFIRuntimeGetNextVariableName", > + "Failed to get next variable name with UEFI runtime service."); > + fwts_uefi_print_status_info(fw, status); > + goto err; > + } > + > + item = malloc(sizeof(*item)); > + if (!item) { > + fwts_failed(fw, LOG_LEVEL_HIGH, "UEFIRuntimeGetNextVariableName", > + "Failed to allocate memory for test."); > + goto err; > + } > + > + item->guid = &vendorguid; > + item->next = NULL; > + > + item->name = malloc(variablenamesize); > + if (!item->name) { > + fwts_failed(fw, LOG_LEVEL_HIGH, "UEFIRuntimeGetNextVariableName", > + "Failed to allocate memory for test."); > + free(item); > + goto err; > + } > + > + memcpy(item->name, variablename, variablenamesize); > + > + /* Ensure there are no duplicate variable names + guid */ > + item->hash = hash_func(variablename, variablenamesize); > + > + if (bucket_insert(item)) { > + fwts_failed(fw, LOG_LEVEL_HIGH, "UEFIRuntimeGetNextVariableName", > + "Duplicate variable name found."); > + free(item->name); > + free(item); > + goto err; > + } > + }; > + > + bucket_destroy(); > + return FWTS_OK; > + > +err: > + bucket_destroy(); > return FWTS_ERROR; > } > > @@ -931,6 +1082,10 @@ static int uefirtvariable_test2(fwts_framework *fw) > if (ret != FWTS_OK) > return ret; > > + ret = getnextvariable_test3(fw); > + if (ret != FWTS_OK) > + return ret; > + > fwts_passed(fw, "UEFI runtime service GetNextVariableName interface test passed."); > > return FWTS_OK; > Acked-by: Ivan Hu <ivan.hu@canonical.com>
diff --git a/src/uefi/uefirtvariable/uefirtvariable.c b/src/uefi/uefirtvariable/uefirtvariable.c index 177dbf9..fe4cdce 100644 --- a/src/uefi/uefirtvariable/uefirtvariable.c +++ b/src/uefi/uefirtvariable/uefirtvariable.c @@ -401,7 +401,158 @@ static int getnextvariable_test2(fwts_framework *fw) return FWTS_OK; err: + return FWTS_ERROR; +} + +struct efi_var_item { + struct efi_var_item *next; /* collision chain */ + uint16_t *name; + EFI_GUID *guid; + uint64_t hash; +}; + +/* + * This is a completely arbitrary value. + */ +#define BUCKET_SIZE 32 +static struct efi_var_item *buckets[BUCKET_SIZE]; + +/* + * This doesn't have to be a super efficient hashing function with + * minimal collisions, just more efficient than iterating over a + * simple linked list. + */ +static inline uint64_t hash_func(uint16_t *variablename, uint64_t length) +{ + uint64_t i, hash = 0; + uint16_t *c = variablename; + + for (i = 0; i < length; i++) + hash = hash * 33 + *c++; + + return hash; +} + +/* + * Return's 0 on success, -1 if there was a collision - meaning we've + * encountered duplicate variable names with the same GUID. + */ +static int bucket_insert(struct efi_var_item *item) +{ + struct efi_var_item *chain; + unsigned int index = item->hash % BUCKET_SIZE; + + chain = buckets[index]; + + while (chain) { + /* + * OK, we got a collision - no big deal. Walk the + * chain and see whether this variable name and + * variable guid already appear on it. + */ + if (compare_name(item->name, chain->name)) { + if (compare_guid(item->guid, chain->guid)) + return -1; /* duplicate */ + } + + chain = chain->next; + } + + item->next = buckets[index]; + buckets[index] = item; + return 0; +} + +static void bucket_destroy(void) +{ + struct efi_var_item *item; + int i; + + for (i = 0; i < BUCKET_SIZE; i++) { + item = buckets[i]; + + while (item) { + struct efi_var_item *chain = item->next; + + free(item->name); + free(item); + item = chain; + } + } +} + +static int getnextvariable_test3(fwts_framework *fw) +{ + long ioret; + uint64_t status; + struct efi_getnextvariablename getnextvariablename; + uint64_t variablenamesize = MAX_DATA_LENGTH; + uint16_t variablename[MAX_DATA_LENGTH]; + EFI_GUID vendorguid; + + getnextvariablename.VariableNameSize = &variablenamesize; + getnextvariablename.VariableName = variablename; + getnextvariablename.VendorGuid = &vendorguid; + getnextvariablename.status = &status; + + /* To start the search, need to pass a Null-terminated string in VariableName */ + variablename[0] = '\0'; + while (true) { + struct efi_var_item *item; + + variablenamesize = MAX_DATA_LENGTH; + ioret = ioctl(fd, EFI_RUNTIME_GET_NEXTVARIABLENAME, &getnextvariablename); + + if (ioret == -1) { + + /* no next variable was found*/ + if (*getnextvariablename.status == EFI_NOT_FOUND) + break; + + fwts_failed(fw, LOG_LEVEL_HIGH, "UEFIRuntimeGetNextVariableName", + "Failed to get next variable name with UEFI runtime service."); + fwts_uefi_print_status_info(fw, status); + goto err; + } + + item = malloc(sizeof(*item)); + if (!item) { + fwts_failed(fw, LOG_LEVEL_HIGH, "UEFIRuntimeGetNextVariableName", + "Failed to allocate memory for test."); + goto err; + } + + item->guid = &vendorguid; + item->next = NULL; + + item->name = malloc(variablenamesize); + if (!item->name) { + fwts_failed(fw, LOG_LEVEL_HIGH, "UEFIRuntimeGetNextVariableName", + "Failed to allocate memory for test."); + free(item); + goto err; + } + + memcpy(item->name, variablename, variablenamesize); + + /* Ensure there are no duplicate variable names + guid */ + item->hash = hash_func(variablename, variablenamesize); + + if (bucket_insert(item)) { + fwts_failed(fw, LOG_LEVEL_HIGH, "UEFIRuntimeGetNextVariableName", + "Duplicate variable name found."); + free(item->name); + free(item); + goto err; + } + }; + + bucket_destroy(); + return FWTS_OK; + +err: + bucket_destroy(); return FWTS_ERROR; } @@ -931,6 +1082,10 @@ static int uefirtvariable_test2(fwts_framework *fw) if (ret != FWTS_OK) return ret; + ret = getnextvariable_test3(fw); + if (ret != FWTS_OK) + return ret; + fwts_passed(fw, "UEFI runtime service GetNextVariableName interface test passed."); return FWTS_OK;