1/** @file 2 A simple "fuzzer" application for OrderedCollectionLib, reading commands from 3 the standard input, and writing results to the standard output. 4 5 Make sure you configure your platform so that the console stderr device is 6 visible to the user (or else run the program from wherever stderr is visible 7 per default, eg. serial line). 8 9 Copyright (C) 2014, Red Hat, Inc. 10 Copyright (c) 2010 - 2011, Intel Corporation. All rights reserved.<BR> 11 12 This program and the accompanying materials are licensed and made available 13 under the terms and conditions of the BSD License which accompanies this 14 distribution. The full text of the license may be found at 15 http://opensource.org/licenses/bsd-license. 16 17 THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS, WITHOUT 18 WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED. 19**/ 20 21#include <assert.h> // assert() 22#include <errno.h> // errno 23#include <limits.h> // INT_MIN 24#include <stdio.h> // fgets() 25#include <stdlib.h> // EXIT_FAILURE 26#include <string.h> // strerror() 27#include <unistd.h> // getopt() 28 29#include <Library/OrderedCollectionLib.h> 30 31// 32// We allow the user to select between stdin+stdout and regular input+output 33// files via command line options. We don't rely on shell redirection for two 34// reasons: 35// 36// - The "old shell" doesn't support input redirection (<a, <); 37// 38// - The "new shell" supports input redirection (<a, <), but those redirections 39// break fgets(stdin). Both when redirecting stdin from an ASCII file (<a), 40// and when redirecting stdin from a UCS-2 file (<), the very first fgets() 41// spirals into an infinite loop, spewing ^@ on the serial console. 42// 43// Performing fopen() manually (made available to the user with the -i option), 44// and reading from that stream with fgets() work under both old and new shell. 45// Only ASCII encoded files are supported. 46// 47static FILE *Input, *Output; 48 49 50// 51// Define a (potentially aggregate) key type. 52// 53typedef struct { 54 int Value; 55} USER_KEY; 56 57// 58// The user structure includes the key as one of its fields. (There can be 59// several, optionally differently typed, keys, if we link user structures into 60// several collections, with different comparators.) 61// 62typedef struct { 63 unsigned char Supplementary1[4]; 64 USER_KEY Key; 65 unsigned short Supplementary2[2]; 66} USER_STRUCT; 67 68 69/** 70 Compare a standalone key against a user structure containing an embedded key. 71 72 @param[in] StandaloneKey Pointer to the bare key. 73 74 @param[in] UserStruct Pointer to the user structure with the embedded 75 key. 76 77 @retval <0 If StandaloneKey compares less than UserStruct's key. 78 79 @retval 0 If StandaloneKey compares equal to UserStruct's key. 80 81 @retval >0 If StandaloneKey compares greater than UserStruct's key. 82**/ 83static 84INTN 85EFIAPI 86KeyCompare ( 87 IN CONST VOID *StandaloneKey, 88 IN CONST VOID *UserStruct 89 ) 90{ 91 const USER_KEY *CmpKey; 92 const USER_STRUCT *CmpStruct; 93 94 CmpKey = StandaloneKey; 95 CmpStruct = UserStruct; 96 97 return CmpKey->Value < CmpStruct->Key.Value ? -1 : 98 CmpKey->Value > CmpStruct->Key.Value ? 1 : 99 0; 100} 101 102 103/** 104 Comparator function type for two user structures. 105 106 @param[in] UserStruct1 Pointer to the first user structure. 107 108 @param[in] UserStruct2 Pointer to the second user structure. 109 110 @retval <0 If UserStruct1 compares less than UserStruct2. 111 112 @retval 0 If UserStruct1 compares equal to UserStruct2. 113 114 @retval >0 If UserStruct1 compares greater than UserStruct2. 115**/ 116static 117INTN 118EFIAPI 119UserStructCompare ( 120 IN CONST VOID *UserStruct1, 121 IN CONST VOID *UserStruct2 122 ) 123{ 124 const USER_STRUCT *CmpStruct1; 125 126 CmpStruct1 = UserStruct1; 127 return KeyCompare (&CmpStruct1->Key, UserStruct2); 128} 129 130 131/** 132 Empty the collection by iterating forward through its entries. 133 134 This function demonstrates that iterators different from the one being 135 removed remain valid. 136 137 @param[in,out] Collection The collection to empty. 138**/ 139static void 140CmdForwardEmpty ( 141 IN OUT ORDERED_COLLECTION *Collection 142 ) 143{ 144 ORDERED_COLLECTION_ENTRY *Entry; 145 146 Entry = OrderedCollectionMin (Collection); 147 while (Entry != NULL) { 148 ORDERED_COLLECTION_ENTRY *Next; 149 void *Ptr; 150 USER_STRUCT *UserStruct; 151 152 Next = OrderedCollectionNext (Entry); 153 OrderedCollectionDelete (Collection, Entry, &Ptr); 154 155 UserStruct = Ptr; 156 fprintf (Output, "%s: %d: removed\n", __FUNCTION__, UserStruct->Key.Value); 157 free (UserStruct); 158 159 Entry = Next; 160 } 161} 162 163 164/** 165 Empty the collection by iterating backward through its entries. 166 167 This function demonstrates that iterators different from the one being 168 removed remain valid. 169 170 @param[in,out] Collection The collection to empty. 171**/ 172static void 173CmdBackwardEmpty ( 174 IN OUT ORDERED_COLLECTION *Collection 175 ) 176{ 177 ORDERED_COLLECTION_ENTRY *Entry; 178 179 Entry = OrderedCollectionMax (Collection); 180 while (Entry != NULL) { 181 ORDERED_COLLECTION_ENTRY *Prev; 182 void *Ptr; 183 USER_STRUCT *UserStruct; 184 185 Prev = OrderedCollectionPrev (Entry); 186 OrderedCollectionDelete (Collection, Entry, &Ptr); 187 188 UserStruct = Ptr; 189 fprintf (Output, "%s: %d: removed\n", __FUNCTION__, UserStruct->Key.Value); 190 free (UserStruct); 191 192 Entry = Prev; 193 } 194} 195 196 197/** 198 List the user structures linked into the collection, in increasing order. 199 200 @param[in] Collection The collection to list. 201**/ 202static void 203CmdForwardList ( 204 IN ORDERED_COLLECTION *Collection 205 ) 206{ 207 ORDERED_COLLECTION_ENTRY *Entry; 208 209 for (Entry = OrderedCollectionMin (Collection); Entry != NULL; 210 Entry = OrderedCollectionNext (Entry)) { 211 USER_STRUCT *UserStruct; 212 213 UserStruct = OrderedCollectionUserStruct (Entry); 214 fprintf (Output, "%s: %d\n", __FUNCTION__, UserStruct->Key.Value); 215 } 216} 217 218 219/** 220 List the user structures linked into the collection, in decreasing order. 221 222 @param[in] Collection The collection to list. 223**/ 224static void 225CmdBackwardList ( 226 IN ORDERED_COLLECTION *Collection 227 ) 228{ 229 ORDERED_COLLECTION_ENTRY *Entry; 230 231 for (Entry = OrderedCollectionMax (Collection); Entry != NULL; 232 Entry = OrderedCollectionPrev (Entry)) { 233 USER_STRUCT *UserStruct; 234 235 UserStruct = OrderedCollectionUserStruct (Entry); 236 fprintf (Output, "%s: %d\n", __FUNCTION__, UserStruct->Key.Value); 237 } 238} 239 240 241/** 242 Create a new user structure and attempt to insert it into the collection. 243 244 @param[in] Value The key value of the user structure to create. 245 246 @param[in,out] Collection The collection to insert the new user structure 247 into. 248**/ 249static void 250CmdInsert ( 251 IN int Value, 252 IN OUT ORDERED_COLLECTION *Collection 253 ) 254{ 255 USER_STRUCT *UserStruct, *UserStruct2; 256 RETURN_STATUS Status; 257 ORDERED_COLLECTION_ENTRY *Entry; 258 259 UserStruct = calloc (1, sizeof *UserStruct); 260 if (UserStruct == NULL) { 261 fprintf (Output, "%s: %d: calloc(): out of memory\n", __FUNCTION__, Value); 262 return; 263 } 264 265 UserStruct->Key.Value = Value; 266 Status = OrderedCollectionInsert (Collection, &Entry, UserStruct); 267 268 switch (Status) { 269 case RETURN_OUT_OF_RESOURCES: 270 fprintf (Output, "%s: %d: OrderedCollectionInsert(): out of memory\n", 271 __FUNCTION__, Value); 272 goto ReleaseUserStruct; 273 274 case RETURN_ALREADY_STARTED: 275 UserStruct2 = OrderedCollectionUserStruct (Entry); 276 assert (UserStruct != UserStruct2); 277 assert (UserStruct2->Key.Value == Value); 278 fprintf (Output, "%s: %d: already exists\n", __FUNCTION__, 279 UserStruct2->Key.Value); 280 goto ReleaseUserStruct; 281 282 default: 283 assert (Status == RETURN_SUCCESS); 284 break; 285 } 286 287 assert (OrderedCollectionUserStruct (Entry) == UserStruct); 288 fprintf (Output, "%s: %d: inserted\n", __FUNCTION__, Value); 289 return; 290 291ReleaseUserStruct: 292 free (UserStruct); 293} 294 295 296/** 297 Look up a user structure by key in the collection and print it. 298 299 @param[in] Value The key of the user structure to find. 300 301 @param[in] Collection The collection to search for the user structure with 302 the key. 303**/ 304static void 305CmdFind ( 306 IN int Value, 307 IN ORDERED_COLLECTION *Collection 308 ) 309{ 310 USER_KEY StandaloneKey; 311 ORDERED_COLLECTION_ENTRY *Entry; 312 USER_STRUCT *UserStruct; 313 314 StandaloneKey.Value = Value; 315 Entry = OrderedCollectionFind (Collection, &StandaloneKey); 316 317 if (Entry == NULL) { 318 fprintf (Output, "%s: %d: not found\n", __FUNCTION__, Value); 319 return; 320 } 321 322 UserStruct = OrderedCollectionUserStruct (Entry); 323 assert (UserStruct->Key.Value == StandaloneKey.Value); 324 fprintf (Output, "%s: %d: found\n", __FUNCTION__, UserStruct->Key.Value); 325} 326 327 328/** 329 Look up a user structure by key in the collection and delete it. 330 331 @param[in] Value The key of the user structure to find. 332 333 @param[in] Collection The collection to search for the user structure with 334 the key. 335**/ 336static void 337CmdDelete ( 338 IN int Value, 339 IN ORDERED_COLLECTION *Collection 340 ) 341{ 342 USER_KEY StandaloneKey; 343 ORDERED_COLLECTION_ENTRY *Entry; 344 void *Ptr; 345 USER_STRUCT *UserStruct; 346 347 StandaloneKey.Value = Value; 348 Entry = OrderedCollectionFind (Collection, &StandaloneKey); 349 350 if (Entry == NULL) { 351 fprintf (Output, "%s: %d: not found\n", __FUNCTION__, Value); 352 return; 353 } 354 355 OrderedCollectionDelete (Collection, Entry, &Ptr); 356 357 UserStruct = Ptr; 358 assert (UserStruct->Key.Value == StandaloneKey.Value); 359 fprintf (Output, "%s: %d: removed\n", __FUNCTION__, UserStruct->Key.Value); 360 free (UserStruct); 361} 362 363 364typedef struct { 365 const char *Command; 366 void (*Function) (ORDERED_COLLECTION *Collection); 367 const char *Description; 368} KEYLESS_COMMAND; 369 370typedef struct { 371 const char *Command; 372 void (*Function) (int Value, ORDERED_COLLECTION *Collection); 373 const char *Description; 374} KEYED_COMMAND; 375 376static const KEYLESS_COMMAND KeylessCommands[] = { 377 { "forward-empty", CmdForwardEmpty, 378 "empty the collection iterating forward" }, 379 { "fe", CmdForwardEmpty, 380 "shorthand for forward-empty" }, 381 { "backward-empty", CmdBackwardEmpty, 382 "empty the collection iterating backward" }, 383 { "be", CmdBackwardEmpty, 384 "shorthand for backward-empty" }, 385 { "forward-list", CmdForwardList, 386 "list contents, iterating forward" }, 387 { "fl", CmdForwardList, 388 "shorthand for forward-list" }, 389 { "backward-list", CmdBackwardList, 390 "list contents, iterating backward" }, 391 { "bl", CmdBackwardList, 392 "shorthand for backward-list" }, 393 { NULL } 394}; 395 396static const KEYED_COMMAND KeyedCommands[] = { 397 { "insert ", CmdInsert, "insert value into collection" }, 398 { "i ", CmdInsert, "shorthand for insert" }, 399 { "find ", CmdFind, "find value in collection" }, 400 { "f ", CmdFind, "shorthand for find" }, 401 { "delete ", CmdDelete, "delete value from collection" }, 402 { "d ", CmdDelete, "shorthand for delete" }, 403 { NULL } 404}; 405 406 407/** 408 List the supported commands on stderr. 409**/ 410static void 411ListCommands ( 412 void 413 ) 414{ 415 const KEYLESS_COMMAND *KeylessCmd; 416 const KEYED_COMMAND *KeyedCmd; 417 418 fprintf (stderr, "Supported commands:\n\n"); 419 for (KeylessCmd = KeylessCommands; KeylessCmd->Command != NULL; 420 ++KeylessCmd) { 421 fprintf (stderr, "%-14s: %s\n", KeylessCmd->Command, 422 KeylessCmd->Description); 423 } 424 for (KeyedCmd = KeyedCommands; KeyedCmd->Command != NULL; ++KeyedCmd) { 425 fprintf (stderr, "%-9s<int>: %s\n", KeyedCmd->Command, 426 KeyedCmd->Description); 427 } 428} 429 430 431/** 432 Configure stdio FILEs that we'll use for input and output. 433 434 @param[in] ArgC The number of elements in ArgV, from main(). The environment 435 is required to ensure ArgC >= 1 (ie. that the program name, 436 ArgV[0], is available). 437 438 @param[in] ArgV Command line argument list, from main(). 439**/ 440static void 441SetupInputOutput ( 442 IN int ArgC, 443 IN char **ArgV 444 ) 445{ 446 char *InputName, *OutputName; 447 int Loop; 448 449 assert (ArgC >= 1); 450 451 InputName = NULL; 452 OutputName = NULL; 453 Loop = 1; 454 455 while (Loop) { 456 switch (getopt (ArgC, ArgV, ":i:o:h")) { 457 case 'i': 458 InputName = optarg; 459 break; 460 461 case 'o': 462 OutputName = optarg; 463 break; 464 465 case 'h': 466 fprintf (stderr, 467 "%1$s: simple OrderedCollectionLib tester\n" 468 "\n" 469 "Usage: 1. %1$s [-i InputFile] [-o OutputFile]\n" 470 " 2. %1$s -h\n" 471 "\n" 472 "Options:\n" 473 " -i InputFile : read commands from InputFile\n" 474 " (will read from stdin if absent)\n" 475 " -o OutputFile: write command responses to OutputFile\n" 476 " (will write to stdout if absent)\n" 477 " -h : print this help and exit\n" 478 "\n", ArgV[0]); 479 ListCommands (); 480 exit (EXIT_SUCCESS); 481 482// 483// The current "compatibility" getopt() implementation doesn't support optopt, 484// but it gracefully degrades these branches to the others (one of the optarg 485// ones or the excess operands one). 486// 487#if 0 488 case ':': 489 fprintf (stderr, "%s: option -%c requires an argument; pass -h for " 490 "help\n", ArgV[0], optopt); 491 exit (EXIT_FAILURE); 492 493 case '?': 494 fprintf (stderr, "%s: unknown option -%c; pass -h for help\n", ArgV[0], 495 optopt); 496 exit (EXIT_FAILURE); 497#endif 498 499 case -1: 500 if (optind != ArgC) { 501 fprintf (stderr, "%s: excess operands on command line; pass -h for " 502 "help\n", ArgV[0]); 503 exit (EXIT_FAILURE); 504 } 505 Loop = 0; 506 break; 507 508 default: 509 assert (0); 510 } 511 } 512 513 if (InputName == NULL) { 514 Input = stdin; 515 } else { 516 Input = fopen (InputName, "r"); 517 if (Input == NULL) { 518 fprintf (stderr, "%s: fopen(\"%s\", \"r\"): %s\n", ArgV[0], InputName, 519 strerror (errno)); 520 exit (EXIT_FAILURE); 521 } 522 } 523 524 if (OutputName == NULL) { 525 Output = stdout; 526 } else { 527 Output = fopen (OutputName, "w"); 528 if (Output == NULL) { 529 fprintf (stderr, "%s: fopen(\"%s\", \"w\"): %s\n", ArgV[0], OutputName, 530 strerror (errno)); 531 exit (EXIT_FAILURE); 532 } 533 } 534 535 // 536 // When reading commands from the standard input, assume interactive mode, 537 // and list the supported commands. However, delay this until both streams 538 // are set up. 539 // 540 if (InputName == NULL) { 541 ListCommands (); 542 } 543} 544 545 546int 547main ( 548 IN int ArgC, 549 IN char **ArgV 550 ) 551{ 552 int RetVal; 553 ORDERED_COLLECTION *Collection; 554 char Line[256]; 555 556 SetupInputOutput (ArgC, ArgV); 557 558 Collection = OrderedCollectionInit (UserStructCompare, KeyCompare); 559 if (Collection == NULL) { 560 fprintf (stderr, "%s: OrderedCollectionInit(): out of memory\n", 561 __FUNCTION__); 562 return EXIT_FAILURE; 563 } 564 565 RetVal = EXIT_SUCCESS; 566 while (fgets (Line, sizeof Line, Input) != NULL) { 567 size_t Length; 568 const KEYLESS_COMMAND *KeylessCmd; 569 const KEYED_COMMAND *KeyedCmd; 570 571 Length = strlen (Line); 572 assert (Length > 0); 573 if (Line[Length - 1] != '\n') { 574 fprintf (stderr, "%s: overlong line\n", __FUNCTION__); 575 RetVal = EXIT_FAILURE; 576 break; 577 } 578 579 // 580 // Strip [\r]\n. 581 // 582 Line[Length - 1] = '\0'; 583 if (Length >= 2 && Line[Length - 2] == '\r') { 584 Line[Length - 2] = '\0'; 585 } 586 // 587 // Ignore empty lines and comments. 588 // 589 if (Line[0] == '\0' || Line[0] == '#') { 590 if (Input != stdin) { 591 // 592 // ... but echo them back in non-interactive mode. 593 // 594 fprintf (Output, "%s\n", Line); 595 } 596 continue; 597 } 598 599 // 600 // Ironically, this is the kind of loop that should be replaced with an 601 // ORDERED_COLLECTION. 602 // 603 for (KeylessCmd = KeylessCommands; KeylessCmd->Command != NULL; 604 ++KeylessCmd) { 605 if (strcmp (KeylessCmd->Command, Line) == 0) { 606 KeylessCmd->Function (Collection); 607 break; 608 } 609 } 610 if (KeylessCmd->Command != NULL) { 611 continue; 612 } 613 614 for (KeyedCmd = KeyedCommands; KeyedCmd->Command != NULL; ++KeyedCmd) { 615 size_t CmdLength; 616 617 CmdLength = strlen (KeyedCmd->Command); 618 assert (CmdLength >= 2); 619 if (strncmp (KeyedCmd->Command, Line, CmdLength) == 0) { 620 char *CommandArg, *EndPtr; 621 long Value; 622 623 CommandArg = Line + CmdLength; 624 errno = 0; 625 Value = strtol (CommandArg, &EndPtr, 10); 626 if (EndPtr == CommandArg || // no conversion performed 627 errno != 0 || // not in long's range, etc 628 *EndPtr != '\0' || // final string not empty 629 Value < INT_MIN || Value > INT_MAX // parsed long not in int range 630 ) { 631 fprintf (stderr, "%s: %.*s: \"%s\": not an int\n", __FUNCTION__, 632 (int)(CmdLength - 1), Line, CommandArg); 633 } else { 634 KeyedCmd->Function (Value, Collection); 635 } 636 637 break; 638 } 639 } 640 if (KeyedCmd->Command != NULL) { 641 continue; 642 } 643 644 fprintf (stderr, "%s: \"%s\": unknown command\n", __FUNCTION__, Line); 645 } 646 647 if (RetVal == EXIT_SUCCESS && ferror (Input)) { 648 fprintf (stderr, "%s: fgets(): %s\n", __FUNCTION__, strerror (errno)); 649 RetVal = EXIT_FAILURE; 650 } 651 652 CmdForwardEmpty (Collection); 653 OrderedCollectionUninit (Collection); 654 return RetVal; 655} 656