From patchwork Sun Aug 3 15:34:47 2014 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Laszlo Ersek X-Patchwork-Id: 34749 Return-Path: X-Original-To: linaro@patches.linaro.org Delivered-To: linaro@patches.linaro.org Received: from mail-ob0-f197.google.com (mail-ob0-f197.google.com [209.85.214.197]) by ip-10-151-82-157.ec2.internal (Postfix) with ESMTPS id A3C6B2396D for ; Sun, 3 Aug 2014 15:35:24 +0000 (UTC) Received: by mail-ob0-f197.google.com with SMTP id vb8sf31765351obc.0 for ; Sun, 03 Aug 2014 08:35:24 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:delivered-to:from:to:date:message-id:in-reply-to :references:subject:precedence:reply-to:list-id:list-unsubscribe :list-archive:list-post:list-help:list-subscribe:mime-version :errors-to:x-original-sender:x-original-authentication-results :mailing-list:content-type:content-transfer-encoding; bh=8dlMvMaOFMHm28KuAGHEFS+TqF0ujD0PO7arZ+Mkwdw=; b=jtGvOeQajY5TEBuC2UJSoLcrDxU1bO8UpVyc3LX0M5NELT3FUWgmuvBRgWp8Pp46U3 hof0xOYHEnaK1VMaOZHnrRcAbOWHG99/Rbd6mSgoRExee5jAowHn4oGCsbjdMBLiderH BLOuGhd8ApU37Aj5SeCJNoQ9RqCSSfO6eTmtoAv0esICek9W/OOH2cqhz92KnrqCrmu9 xH9f5TXdZGtBVSZMbcDapMUO237ZBu8nkQffFJ3otRj8l5q/OEcN/9vjvoZ05DBK0STh zmWOV8BIdZd0PvBDuGf2Kvq3KMh3LX0GhLrFelTd5sXhoZnDCg0LV+ro3iPPbSMv/LfM KsyA== X-Gm-Message-State: ALoCoQmAFaw1SwyPiTz0C2p37mX9YS/cbPOcTSULhk34hJ5NMMOWgYb4nS6ko+6lymnv4c6mAdPB X-Received: by 10.182.18.8 with SMTP id s8mr6363111obd.21.1407080124324; Sun, 03 Aug 2014 08:35:24 -0700 (PDT) X-BeenThere: patchwork-forward@linaro.org Received: by 10.140.97.52 with SMTP id l49ls1874845qge.69.gmail; Sun, 03 Aug 2014 08:35:24 -0700 (PDT) X-Received: by 10.220.133.13 with SMTP id d13mr104635vct.66.1407080124170; Sun, 03 Aug 2014 08:35:24 -0700 (PDT) Received: from mail-vc0-f179.google.com (mail-vc0-f179.google.com [209.85.220.179]) by mx.google.com with ESMTPS id re13si10809252vcb.8.2014.08.03.08.35.24 for (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Sun, 03 Aug 2014 08:35:24 -0700 (PDT) Received-SPF: pass (google.com: domain of patch+caf_=patchwork-forward=linaro.org@linaro.org designates 209.85.220.179 as permitted sender) client-ip=209.85.220.179; Received: by mail-vc0-f179.google.com with SMTP id hq11so9561312vcb.10 for ; Sun, 03 Aug 2014 08:35:24 -0700 (PDT) X-Received: by 10.220.131.207 with SMTP id y15mr101208vcs.71.1407080124048; Sun, 03 Aug 2014 08:35:24 -0700 (PDT) X-Forwarded-To: patchwork-forward@linaro.org X-Forwarded-For: patch@linaro.org patchwork-forward@linaro.org Delivered-To: patch@linaro.org Received: by 10.221.37.5 with SMTP id tc5csp241871vcb; Sun, 3 Aug 2014 08:35:23 -0700 (PDT) X-Received: by 10.50.80.116 with SMTP id q20mr28888334igx.22.1407080122618; Sun, 03 Aug 2014 08:35:22 -0700 (PDT) Received: from lists.sourceforge.net (lists.sourceforge.net. [216.34.181.88]) by mx.google.com with ESMTPS id h8si34998741icv.33.2014.08.03.08.35.21 for (version=TLSv1 cipher=RC4-SHA bits=128/128); Sun, 03 Aug 2014 08:35:22 -0700 (PDT) Received-SPF: pass (google.com: domain of edk2-devel-bounces@lists.sourceforge.net designates 216.34.181.88 as permitted sender) client-ip=216.34.181.88; Received: from localhost ([127.0.0.1] helo=sfs-ml-2.v29.ch3.sourceforge.com) by sfs-ml-2.v29.ch3.sourceforge.com with esmtp (Exim 4.76) (envelope-from ) id 1XDxoP-0004Il-D9; Sun, 03 Aug 2014 15:35:05 +0000 Received: from sog-mx-2.v43.ch3.sourceforge.com ([172.29.43.192] helo=mx.sourceforge.net) by sfs-ml-2.v29.ch3.sourceforge.com with esmtp (Exim 4.76) (envelope-from ) id 1XDxoM-0004Id-Fs for edk2-devel@lists.sourceforge.net; Sun, 03 Aug 2014 15:35:02 +0000 Received-SPF: pass (sog-mx-2.v43.ch3.sourceforge.com: domain of redhat.com designates 209.132.183.28 as permitted sender) client-ip=209.132.183.28; envelope-from=lersek@redhat.com; helo=mx1.redhat.com; Received: from mx1.redhat.com ([209.132.183.28]) by sog-mx-2.v43.ch3.sourceforge.com with esmtps (TLSv1:AES256-SHA:256) (Exim 4.76) id 1XDxoJ-0002CW-RK for edk2-devel@lists.sourceforge.net; Sun, 03 Aug 2014 15:35:02 +0000 Received: from int-mx10.intmail.prod.int.phx2.redhat.com (int-mx10.intmail.prod.int.phx2.redhat.com [10.5.11.23]) by mx1.redhat.com (8.14.4/8.14.4) with ESMTP id s73FYrEO001844 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK) for ; Sun, 3 Aug 2014 11:34:53 -0400 Received: from lacos-laptop-7.usersys.redhat.com (ovpn-116-30.ams2.redhat.com [10.36.116.30]) by int-mx10.intmail.prod.int.phx2.redhat.com (8.14.4/8.14.4) with ESMTP id s73FYnWe030700 for ; Sun, 3 Aug 2014 11:34:52 -0400 From: Laszlo Ersek To: edk2-devel@lists.sourceforge.net Date: Sun, 3 Aug 2014 17:34:47 +0200 Message-Id: <1407080087-26108-3-git-send-email-lersek@redhat.com> In-Reply-To: <1407080087-26108-1-git-send-email-lersek@redhat.com> References: <1407080087-26108-1-git-send-email-lersek@redhat.com> X-Scanned-By: MIMEDefang 2.68 on 10.5.11.23 X-Spam-Score: -2.2 (--) X-Spam-Report: Spam Filtering performed by mx.sourceforge.net. See http://spamassassin.org/tag/ for more details. -1.5 SPF_CHECK_PASS SPF reports sender host as permitted sender for sender-domain -0.0 SPF_HELO_PASS SPF: HELO matches SPF record -0.0 SPF_PASS SPF: sender matches SPF record -0.7 RP_MATCHES_RCVD Envelope sender domain matches handover relay domain X-Headers-End: 1XDxoJ-0002CW-RK Subject: [edk2] [PATCH 2/2] AppPkg: introduce RbTreeTest X-BeenThere: edk2-devel@lists.sourceforge.net X-Mailman-Version: 2.1.9 Precedence: list Reply-To: edk2-devel@lists.sourceforge.net List-Id: List-Unsubscribe: , List-Archive: List-Post: , List-Help: , List-Subscribe: , MIME-Version: 1.0 Errors-To: edk2-devel-bounces@lists.sourceforge.net X-Removed-Original-Auth: Dkim didn't pass. X-Original-Sender: lersek@redhat.com X-Original-Authentication-Results: mx.google.com; spf=pass (google.com: domain of patch+caf_=patchwork-forward=linaro.org@linaro.org designates 209.85.220.179 as permitted sender) smtp.mail=patch+caf_=patchwork-forward=linaro.org@linaro.org Mailing-list: list patchwork-forward@linaro.org; contact patchwork-forward+owners@linaro.org X-Google-Group-Id: 836684582541 In this patch a small application is added to AppPkg, with the following two goals: - demonstrate how to use RbTreeLib, - allow users to test and "fuzz" RbTreeLib, entering RbTreeLib API "commands" interactively, or providing them from a script file. A shell script is also provided that generates such an RbTreeTest command script. RbTreeTest validates the internal red-black properties of the tree by calling RbTreeLib's RbTreeValidate() function after each read-write operation. The RbTreeTest application's debugging environment is strictly specified in the DSC file, because RbTreeTest is entirely useless for unit testing without full ASSERT() enablement. The RbTreeTest application deliberately doesn't follow the edk2 coding style in the following: - const vs. CONST, - void vs. VOID, - assert() vs. ASSERT(), - calloc() and free() vs. AllocateZeroPool() and FreePool(), - integer types. This is because RbTreeTest is a standard C application, not a UEFI application per se. In particular it relies on stdio. INTN, EFIAPI and CONST VOID are used only in two places, where we provide the comparator callbacks to RbTreeLib. Proper range checking is ensured for integers. The application takes command input from stdin or a file (if the user requests it), sends command output to stdout or a file (if the user requests it), prints debug output to the console (as other AppPkg applications do when debugging is enabled for them), and prints diagnostics to stderr (like well behaved standard C programs should). Input/output selection is implemented manually because the old shell doesn't support input redirection at all, and because the new shell's input redirection does not co-operate with fgets() for the time being. Contributed-under: TianoCore Contribution Agreement 1.0 Signed-off-by: Laszlo Ersek --- AppPkg/Applications/RbTreeTest/RbTreeTest.inf | 42 ++ AppPkg/Applications/RbTreeTest/RbTreeTest.c | 668 ++++++++++++++++++++++++++ AppPkg/AppPkg.dsc | 10 + AppPkg/Applications/RbTreeTest/gentest.sh | 86 ++++ AppPkg/ReadMe.txt | 4 + 5 files changed, 810 insertions(+) create mode 100644 AppPkg/Applications/RbTreeTest/RbTreeTest.inf create mode 100644 AppPkg/Applications/RbTreeTest/RbTreeTest.c create mode 100644 AppPkg/Applications/RbTreeTest/gentest.sh diff --git a/AppPkg/Applications/RbTreeTest/RbTreeTest.inf b/AppPkg/Applications/RbTreeTest/RbTreeTest.inf new file mode 100644 index 0000000..7f86279 --- /dev/null +++ b/AppPkg/Applications/RbTreeTest/RbTreeTest.inf @@ -0,0 +1,42 @@ +## @file +# A simple "fuzzer" application for RbTreeLib, reading commands from the +# standard input, and writing results to the standard output. +# +# Copyright (C) 2014, Red Hat, Inc. +# Copyright (c) 2010 - 2011, Intel Corporation. All rights reserved.
+# +# This program and the accompanying materials are licensed and made available +# under the terms and conditions of the BSD License which accompanies this +# distribution. The full text of the license may be found at +# http://opensource.org/licenses/bsd-license. +# +# THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS, +# WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR +# IMPLIED. +## + +[Defines] + INF_VERSION = 0x00010006 + BASE_NAME = RbTreeTest + FILE_GUID = E6C7EBB7-1604-4FCB-8F87-B3A6F48730AE + MODULE_TYPE = UEFI_APPLICATION + VERSION_STRING = 0.1 + ENTRY_POINT = ShellCEntryLib + +# +# VALID_ARCHITECTURES = IA32 X64 IPF +# + +[Sources] + RbTreeTest.c + +[Packages] + StdLib/StdLib.dec + MdePkg/MdePkg.dec + ShellPkg/ShellPkg.dec + +[LibraryClasses] + LibC + LibStdio + DevShell + RbTreeLib diff --git a/AppPkg/Applications/RbTreeTest/RbTreeTest.c b/AppPkg/Applications/RbTreeTest/RbTreeTest.c new file mode 100644 index 0000000..f63f05e --- /dev/null +++ b/AppPkg/Applications/RbTreeTest/RbTreeTest.c @@ -0,0 +1,668 @@ +/** @file + A simple "fuzzer" application for RbTreeLib, reading commands from the + standard input, and writing results to the standard output. + + Make sure you configure your platform so that the console stderr device is + visible to the user (or else run the program from wherever stderr is visible + per default, eg. serial line). + + Copyright (C) 2014, Red Hat, Inc. + Copyright (c) 2010 - 2011, Intel Corporation. All rights reserved.
+ + This program and the accompanying materials are licensed and made available + under the terms and conditions of the BSD License which accompanies this + distribution. The full text of the license may be found at + http://opensource.org/licenses/bsd-license. + + THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS, WITHOUT + WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED. +**/ + +#include // assert() +#include // errno +#include // INT_MIN +#include // fgets() +#include // EXIT_FAILURE +#include // strerror() +#include // getopt() + +#include + +// +// We allow the user to select between stdin+stdout and regular input+output +// files via command line options. We don't rely on shell redirection for two +// reasons: +// +// - The "old shell" doesn't support input redirection (0 If StandaloneKey compares greater than UserStruct's key. +**/ +static +INTN +EFIAPI +KeyCompare ( + IN CONST VOID *StandaloneKey, + IN CONST VOID *UserStruct + ) +{ + const USER_KEY *CmpKey; + const USER_STRUCT *CmpStruct; + + CmpKey = StandaloneKey; + CmpStruct = UserStruct; + + return CmpKey->Value < CmpStruct->Key.Value ? -1 : + CmpKey->Value > CmpStruct->Key.Value ? 1 : + 0; +} + + +/** + Comparator function type for two user structures. + + @param[in] UserStruct1 Pointer to the first user structure. + + @param[in] UserStruct2 Pointer to the second user structure. + + @retval <0 If UserStruct1 compares less than UserStruct2. + + @retval 0 If UserStruct1 compares equal to UserStruct2. + + @retval >0 If UserStruct1 compares greater than UserStruct2. +**/ +static +INTN +EFIAPI +UserStructCompare ( + IN CONST VOID *UserStruct1, + IN CONST VOID *UserStruct2 + ) +{ + const USER_STRUCT *CmpStruct1; + + CmpStruct1 = UserStruct1; + return KeyCompare (&CmpStruct1->Key, UserStruct2); +} + + +/** + Tear down the tree by repeatedly removing its root node, while printing and + releasing the associated user structure. + + @param[in,out] Tree The tree to empty. +**/ +static void +TearDown ( + IN OUT RB_TREE *Tree + ) +{ + while (!RbTreeIsEmpty (Tree)) { + void *Ptr; + USER_STRUCT *UserStruct; + + RbTreeDelete (Tree, Tree->Root, &Ptr); + RbTreeValidate (Tree); + + UserStruct = Ptr; + fprintf (Output, "%s: %d: removed via root\n", __FUNCTION__, + UserStruct->Key.Value); + free (UserStruct); + } +} + + +/** + Empty the tree by iterating forward through its nodes. + + This function demonstrates that iterators different from the one being + removed remain valid. + + @param[in,out] Tree The tree to empty. +**/ +static void +CmdForwardEmpty ( + IN OUT RB_TREE *Tree + ) +{ + RB_TREE_NODE *Node; + + Node = RbTreeMin (Tree); + while (Node != NULL) { + RB_TREE_NODE *Next; + void *Ptr; + USER_STRUCT *UserStruct; + + Next = RbTreeNext (Node); + RbTreeDelete (Tree, Node, &Ptr); + RbTreeValidate (Tree); + + UserStruct = Ptr; + fprintf (Output, "%s: %d: removed\n", __FUNCTION__, UserStruct->Key.Value); + free (UserStruct); + + Node = Next; + } +} + + +/** + Empty the tree by iterating backward through its nodes. + + This function demonstrates that iterators different from the one being + removed remain valid. + + @param[in,out] Tree The tree to empty. +**/ +static void +CmdBackwardEmpty ( + IN OUT RB_TREE *Tree + ) +{ + RB_TREE_NODE *Node; + + Node = RbTreeMax (Tree); + while (Node != NULL) { + RB_TREE_NODE *Prev; + void *Ptr; + USER_STRUCT *UserStruct; + + Prev = RbTreePrev (Node); + RbTreeDelete (Tree, Node, &Ptr); + RbTreeValidate (Tree); + + UserStruct = Ptr; + fprintf (Output, "%s: %d: removed\n", __FUNCTION__, UserStruct->Key.Value); + free (UserStruct); + + Node = Prev; + } +} + + +/** + List the user structures linked into the tree, in increasing order. + + @param[in] Tree The tree to list. +**/ +static void +CmdForwardList ( + IN RB_TREE *Tree + ) +{ + RB_TREE_NODE *Node; + + for (Node = RbTreeMin (Tree); Node != NULL; Node = RbTreeNext (Node)) { + USER_STRUCT *UserStruct; + + UserStruct = RbTreeUserStruct (Node); + fprintf (Output, "%s: %d\n", __FUNCTION__, UserStruct->Key.Value); + } +} + + +/** + List the user structures linked into the tree, in decreasing order. + + @param[in] Tree The tree to list. +**/ +static void +CmdBackwardList ( + IN RB_TREE *Tree + ) +{ + RB_TREE_NODE *Node; + + for (Node = RbTreeMax (Tree); Node != NULL; Node = RbTreePrev (Node)) { + USER_STRUCT *UserStruct; + + UserStruct = RbTreeUserStruct (Node); + fprintf (Output, "%s: %d\n", __FUNCTION__, UserStruct->Key.Value); + } +} + + +/** + Create a new user structure and attempt to insert it into the tree. + + @param[in] Value The key value of the user structure to create. + + @param[in,out] Tree The tree to insert the new user structure into. +**/ +static void +CmdInsert ( + IN int Value, + IN OUT RB_TREE *Tree + ) +{ + USER_STRUCT *UserStruct, *UserStruct2; + EFI_STATUS Status; + RB_TREE_NODE *Node; + + UserStruct = calloc (1, sizeof *UserStruct); + if (UserStruct == NULL) { + fprintf (Output, "%s: %d: calloc(): out of memory\n", __FUNCTION__, Value); + return; + } + + UserStruct->Key.Value = Value; + Status = RbTreeInsert (Tree, &Node, UserStruct); + RbTreeValidate (Tree); + + switch (Status) { + case EFI_OUT_OF_RESOURCES: + fprintf (Output, "%s: %d: RbTreeInsert(): out of memory\n", __FUNCTION__, + Value); + goto ReleaseUserStruct; + + case EFI_ALREADY_STARTED: + UserStruct2 = RbTreeUserStruct (Node); + assert (UserStruct != UserStruct2); + assert (UserStruct2->Key.Value == Value); + fprintf (Output, "%s: %d: already exists\n", __FUNCTION__, + UserStruct2->Key.Value); + goto ReleaseUserStruct; + + default: + assert (Status == EFI_SUCCESS); + break; + } + + assert (RbTreeUserStruct (Node) == UserStruct); + fprintf (Output, "%s: %d: inserted\n", __FUNCTION__, Value); + return; + +ReleaseUserStruct: + free (UserStruct); +} + + +/** + Look up a user structure by key in the tree and print it. + + @param[in] Value The key of the user structure to find. + + @param[in] Tree The tree to search for the user structure with the key. +**/ +static void +CmdFind ( + IN int Value, + IN RB_TREE *Tree + ) +{ + USER_KEY StandaloneKey; + RB_TREE_NODE *Node; + USER_STRUCT *UserStruct; + + StandaloneKey.Value = Value; + Node = RbTreeFind (Tree, &StandaloneKey); + + if (Node == NULL) { + fprintf (Output, "%s: %d: not found\n", __FUNCTION__, Value); + return; + } + + UserStruct = RbTreeUserStruct (Node); + assert (UserStruct->Key.Value == StandaloneKey.Value); + fprintf (Output, "%s: %d: found\n", __FUNCTION__, UserStruct->Key.Value); +} + + +/** + Look up a user structure by key in the tree and delete it. + + @param[in] Value The key of the user structure to find. + + @param[in] Tree The tree to search for the user structure with the key. +**/ +static void +CmdDelete ( + IN int Value, + IN RB_TREE *Tree + ) +{ + USER_KEY StandaloneKey; + RB_TREE_NODE *Node; + void *Ptr; + USER_STRUCT *UserStruct; + + StandaloneKey.Value = Value; + Node = RbTreeFind (Tree, &StandaloneKey); + + if (Node == NULL) { + fprintf (Output, "%s: %d: not found\n", __FUNCTION__, Value); + return; + } + + RbTreeDelete (Tree, Node, &Ptr); + RbTreeValidate (Tree); + + UserStruct = Ptr; + assert (UserStruct->Key.Value == StandaloneKey.Value); + fprintf (Output, "%s: %d: removed\n", __FUNCTION__, UserStruct->Key.Value); + free (UserStruct); +} + + +typedef struct { + const char *Command; + void (*Function) (RB_TREE *Tree); + const char *Description; +} KEYLESS_COMMAND; + +typedef struct { + const char *Command; + void (*Function) (int Value, RB_TREE *Tree); + const char *Description; +} KEYED_COMMAND; + +static const KEYLESS_COMMAND KeylessCommands[] = { + { "forward-empty", CmdForwardEmpty, "empty the tree iterating forward" }, + { "fe", CmdForwardEmpty, "shorthand for forward-empty" }, + { "backward-empty", CmdBackwardEmpty, "empty the tree iterating backward" }, + { "be", CmdBackwardEmpty, "shorthand for backward-empty" }, + { "forward-list", CmdForwardList, "list contents, iterating forward" }, + { "fl", CmdForwardList, "shorthand for forward-list" }, + { "backward-list", CmdBackwardList, "list contents, iterating backward" }, + { "bl", CmdBackwardList, "shorthand for backward-list" }, + { NULL } +}; + +static const KEYED_COMMAND KeyedCommands[] = { + { "insert ", CmdInsert, "insert value into tree" }, + { "i ", CmdInsert, "shorthand for insert" }, + { "find ", CmdFind, "find value in tree" }, + { "f ", CmdFind, "shorthand for find" }, + { "delete ", CmdDelete, "delete value from tree" }, + { "d ", CmdDelete, "shorthand for delete" }, + { NULL } +}; + + +/** + List the supported commands on stderr. +**/ +static void +ListCommands ( + void + ) +{ + const KEYLESS_COMMAND *KeylessCmd; + const KEYED_COMMAND *KeyedCmd; + + fprintf (stderr, "Supported commands:\n\n"); + for (KeylessCmd = KeylessCommands; KeylessCmd->Command != NULL; + ++KeylessCmd) { + fprintf (stderr, "%-14s: %s\n", KeylessCmd->Command, + KeylessCmd->Description); + } + for (KeyedCmd = KeyedCommands; KeyedCmd->Command != NULL; ++KeyedCmd) { + fprintf (stderr, "%-9s: %s\n", KeyedCmd->Command, + KeyedCmd->Description); + } +} + + +/** + Configure stdio FILEs that we'll use for input and output. + + @param[in] ArgC The number of elements in ArgV, from main(). The environment + is required to ensure ArgC >= 1 (ie. that the program name, + ArgV[0], is available). + + @param[in] ArgV Command line argument list, from main(). +**/ +static void +SetupInputOutput ( + IN int ArgC, + IN char **ArgV + ) +{ + char *InputName, *OutputName; + int Loop; + + assert (ArgC >= 1); + + InputName = NULL; + OutputName = NULL; + Loop = 1; + + while (Loop) { + switch (getopt (ArgC, ArgV, ":i:o:h")) { + case 'i': + InputName = optarg; + break; + + case 'o': + OutputName = optarg; + break; + + case 'h': + fprintf (stderr, + "%1$s: simple RbTreeLib tester\n" + "\n" + "Usage: 1. %1$s [-i InputFile] [-o OutputFile]\n" + " 2. %1$s -h\n" + "\n" + "Options:\n" + " -i InputFile : read commands from InputFile\n" + " (will read from stdin if absent)\n" + " -o OutputFile: write command responses to OutputFile\n" + " (will write to stdout if absent)\n" + " -h : print this help and exit\n" + "\n", ArgV[0]); + ListCommands (); + exit (EXIT_SUCCESS); + +// +// The current "compatibility" getopt() implementation doesn't support optopt, +// but it gracefully degrades these branches to the others (one of the optarg +// ones or the excess operands one). +// +#if 0 + case ':': + fprintf (stderr, "%s: option -%c requires an argument; pass -h for " + "help\n", ArgV[0], optopt); + exit (EXIT_FAILURE); + + case '?': + fprintf (stderr, "%s: unknown option -%c; pass -h for help\n", ArgV[0], + optopt); + exit (EXIT_FAILURE); +#endif + + case -1: + if (optind != ArgC) { + fprintf (stderr, "%s: excess operands on command line; pass -h for " + "help\n", ArgV[0]); + exit (EXIT_FAILURE); + } + Loop = 0; + break; + + default: + assert (0); + } + } + + if (InputName == NULL) { + Input = stdin; + } else { + Input = fopen (InputName, "r"); + if (Input == NULL) { + fprintf (stderr, "%s: fopen(\"%s\", \"r\"): %s\n", ArgV[0], InputName, + strerror (errno)); + exit (EXIT_FAILURE); + } + } + + if (OutputName == NULL) { + Output = stdout; + } else { + Output = fopen (OutputName, "w"); + if (Output == NULL) { + fprintf (stderr, "%s: fopen(\"%s\", \"w\"): %s\n", ArgV[0], OutputName, + strerror (errno)); + exit (EXIT_FAILURE); + } + } + + // + // When reading commands from the standard input, assume interactive mode, + // and list the supported commands. However, delay this until both streams + // are set up. + // + if (InputName == NULL) { + ListCommands (); + } +} + + +int +main ( + IN int ArgC, + IN char **ArgV + ) +{ + int RetVal; + RB_TREE Tree; + char Line[256]; + + SetupInputOutput (ArgC, ArgV); + RetVal = EXIT_SUCCESS; + + RbTreeInit (&Tree, UserStructCompare, KeyCompare); + RbTreeValidate (&Tree); + + while (fgets (Line, sizeof Line, Input) != NULL) { + size_t Length; + const KEYLESS_COMMAND *KeylessCmd; + const KEYED_COMMAND *KeyedCmd; + + Length = strlen (Line); + assert (Length > 0); + if (Line[Length - 1] != '\n') { + fprintf (stderr, "%s: overlong line\n", __FUNCTION__); + RetVal = EXIT_FAILURE; + break; + } + + // + // Strip [\r]\n. + // + Line[Length - 1] = '\0'; + if (Length >= 2 && Line[Length - 2] == '\r') { + Line[Length - 2] = '\0'; + } + // + // Ignore empty lines and comments. + // + if (Line[0] == '\0' || Line[0] == '#') { + if (Input != stdin) { + // + // ... but echo them back in non-interactive mode. + // + fprintf (Output, "%s\n", Line); + } + continue; + } + + // + // Ironically, this is the kind of loop that should be replaced with an + // RB_TREE. + // + for (KeylessCmd = KeylessCommands; KeylessCmd->Command != NULL; + ++KeylessCmd) { + if (strcmp (KeylessCmd->Command, Line) == 0) { + KeylessCmd->Function (&Tree); + break; + } + } + if (KeylessCmd->Command != NULL) { + continue; + } + + for (KeyedCmd = KeyedCommands; KeyedCmd->Command != NULL; ++KeyedCmd) { + size_t CmdLength; + + CmdLength = strlen (KeyedCmd->Command); + assert (CmdLength >= 2); + if (strncmp (KeyedCmd->Command, Line, CmdLength) == 0) { + char *CommandArg, *EndPtr; + long Value; + + CommandArg = Line + CmdLength; + errno = 0; + Value = strtol (CommandArg, &EndPtr, 10); + if (EndPtr == CommandArg || // no conversion performed + errno != 0 || // not in long's range, etc + *EndPtr != '\0' || // final string not empty + Value < INT_MIN || Value > INT_MAX // parsed long not in int range + ) { + fprintf (stderr, "%s: %.*s: \"%s\": not an int\n", __FUNCTION__, + (int)(CmdLength - 1), Line, CommandArg); + } else { + KeyedCmd->Function (Value, &Tree); + } + + break; + } + } + if (KeyedCmd->Command != NULL) { + continue; + } + + fprintf (stderr, "%s: \"%s\": unknown command\n", __FUNCTION__, Line); + } + + if (RetVal == EXIT_SUCCESS && ferror (Input)) { + fprintf (stderr, "%s: fgets(): %s\n", __FUNCTION__, strerror (errno)); + RetVal = EXIT_FAILURE; + } + + TearDown (&Tree); + RbTreeUninit (&Tree); + return RetVal; +} diff --git a/AppPkg/AppPkg.dsc b/AppPkg/AppPkg.dsc index d0aac2c..70cbca5 100644 --- a/AppPkg/AppPkg.dsc +++ b/AppPkg/AppPkg.dsc @@ -112,6 +112,16 @@ AppPkg/Applications/Main/Main.inf # Simple invocation. No other LibC functions. AppPkg/Applications/Enquire/Enquire.inf # + AppPkg/Applications/RbTreeTest/RbTreeTest.inf { # A simple RbTreeLib fuzzer. + + RbTreeLib|MdePkg/Library/BaseRbTreeLib/BaseRbTreeLib.inf + DebugLib|MdePkg/Library/UefiDebugLibConOut/UefiDebugLibConOut.inf + DebugPrintErrorLevelLib|MdePkg/Library/BaseDebugPrintErrorLevelLib/BaseDebugPrintErrorLevelLib.inf + + gEfiMdePkgTokenSpaceGuid.PcdDebugPropertyMask|0x2F + gEfiMdePkgTokenSpaceGuid.PcdDebugPrintErrorLevel|0x80400040 + } + #### After extracting the Python distribution, un-comment the following line to build Python. # AppPkg/Applications/Python/PythonCore.inf diff --git a/AppPkg/Applications/RbTreeTest/gentest.sh b/AppPkg/Applications/RbTreeTest/gentest.sh new file mode 100644 index 0000000..b5aa01c --- /dev/null +++ b/AppPkg/Applications/RbTreeTest/gentest.sh @@ -0,0 +1,86 @@ +## @file +# Small test script generator for RbTreeTest. +# +# Usage: +# - generate script: sh gentest.sh >input.txt +# - run script with tester: RbTreeTest -i input.txt -o output.txt +# +# Copyright (C) 2014, Red Hat, Inc. +# +# This program and the accompanying materials are licensed and made available +# under the terms and conditions of the BSD License which accompanies this +# distribution. The full text of the license may be found at +# http://opensource.org/licenses/bsd-license. +# +# THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS, +# WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR +# IMPLIED. +## + +set -e -u -C + +RANGE_START=0 +RANGE_STOP=9999 + +gen_rnd_insert() +{ + shuf --input-range=$RANGE_START-$RANGE_STOP | sed 's/^/insert /' +} + +gen_rnd_delete() +{ + shuf --input-range=$RANGE_START-$RANGE_STOP | sed 's/^/delete /' +} + +gen_mon_inc_insert() +{ + seq $RANGE_START $RANGE_STOP | sed 's/^/insert /' +} + +gen_mon_inc_delete() +{ + seq $RANGE_START $RANGE_STOP | sed 's/^/delete /' +} + +gen_mon_dec_delete() +{ + seq $RANGE_START $RANGE_STOP | tac | sed 's/^/delete /' +} + +{ + echo '# populate the tree in random order and empty it iterating forward' + gen_rnd_insert + echo forward-empty + + echo + echo '# populate the tree in random order and empty it iterating backward' + gen_rnd_insert + echo backward-empty + + echo + echo '# populate the tree in random order, list it in increasing and' + echo '# decreasing order, then empty it in random order' + gen_rnd_insert + echo forward-list + echo backward-list + gen_rnd_delete + + echo + echo '# populate the tree in monotonically increasing order, then undo it' + echo '# piecewise in the same order' + gen_mon_inc_insert + gen_mon_inc_delete + + echo + echo '# populate the tree in monotonically increasing order, then undo it' + echo '# piecewise in reverse order' + gen_mon_inc_insert + gen_mon_dec_delete + + echo + echo '# populate the tree randomly, trigger a run of collisions, then exit' + echo '# and let TearDown() empty the tree' + gen_rnd_insert + gen_mon_inc_insert +} \ +| unix2dos diff --git a/AppPkg/ReadMe.txt b/AppPkg/ReadMe.txt index 35e3b6a..2c461f6 100644 --- a/AppPkg/ReadMe.txt +++ b/AppPkg/ReadMe.txt @@ -48,6 +48,10 @@ The EADK is comprised of three packages: See the PythonReadMe.txt file, in the Python directory, for information on configuring and building Python. + RbTreeTest A small Standard C Library application that demonstrates the + use of RbTreeLib (a red-black tree library), and allows the user + to "fuzz" RbTreeLib with interactive or scripted API calls. + Sockets A collection of applications demonstrating use of the EDK II Socket Libraries. These applications include: