From patchwork Tue Mar 5 21:54:53 2013 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Matt Fleming X-Patchwork-Id: 225186 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from huckleberry.canonical.com (huckleberry.canonical.com [91.189.94.19]) by ozlabs.org (Postfix) with ESMTP id C500C2C0369 for ; Wed, 6 Mar 2013 08:55:02 +1100 (EST) Received: from localhost ([127.0.0.1] helo=huckleberry.canonical.com) by huckleberry.canonical.com with esmtp (Exim 4.76) (envelope-from ) id 1UCzp7-0001KV-NA; Tue, 05 Mar 2013 21:55:01 +0000 Received: from arkanian.console-pimps.org ([212.110.184.194]) by huckleberry.canonical.com with esmtp (Exim 4.76) (envelope-from ) id 1UCzp5-0001KP-P6 for fwts-devel@lists.ubuntu.com; Tue, 05 Mar 2013 21:54:59 +0000 Received: by arkanian.console-pimps.org (Postfix, from userid 1002) id B28EB6C064; Tue, 5 Mar 2013 21:54:59 +0000 (GMT) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on arkanian.vm.bytemark.co.uk X-Spam-Level: X-Spam-Status: No, score=-1.0 required=5.0 tests=ALL_TRUSTED autolearn=unavailable version=3.3.1 Received: from localhost (unknown [151.224.133.121]) by arkanian.console-pimps.org (Postfix) with ESMTPSA id 0E0016C055; Tue, 5 Mar 2013 21:54:58 +0000 (GMT) From: Matt Fleming To: fwts-devel@lists.ubuntu.com Subject: [PATCH 2/3] uefirtvariable: Test GetNextVariableName() returns unique variables Date: Tue, 5 Mar 2013 21:54:53 +0000 Message-Id: <1362520494-8917-3-git-send-email-matt@console-pimps.org> X-Mailer: git-send-email 1.7.11.7 In-Reply-To: <1362520494-8917-1-git-send-email-matt@console-pimps.org> References: <1362520494-8917-1-git-send-email-matt@console-pimps.org> Cc: Matt Fleming X-BeenThere: fwts-devel@lists.ubuntu.com X-Mailman-Version: 2.1.14 Precedence: list List-Id: Firmware Test Suite Development List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , MIME-Version: 1.0 Errors-To: fwts-devel-bounces@lists.ubuntu.com Sender: fwts-devel-bounces@lists.ubuntu.com From: Matt Fleming 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 Acked-by: Colin Ian King Acked-by: Ivan Hu --- 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;