crypto/property/README.md

   1 Selecting algorithm implementations by properties
   2 =================================================
   3
   4 Properties are associated with algorithms and are used to select between
   5 different implementations dynamically.
   6
   7 This implementation is based on a number of assumptions:
   8
   9 * Property definition is uncommon.  I.e. providers will be loaded and
  10   unloaded relatively infrequently, if at all.
  11
  12 * The number of distinct property names will be small.
  13
  14 * Providers will often give the same implementation properties to most or
  15   all of their implemented algorithms.  E.g. the FIPS property would be set
  16   across an entire provider.  Likewise for, hardware, accelerated, software,
  17   HSM and, perhaps, constant_time.
  18
  19 * There are a lot of algorithm implementations, therefore property
  20   definitions should be space efficient.  However...
  21
  22 * ... property queries are very common.  These must be fast.
  23
  24 * Property queries come from a small set and are reused many times typically.
  25   I.e. an application tends to use the same set of queries over and over,
  26   rather than spanning a wide variety of queries.
  27
  28 * Property queries can never add new property definitions.
  29
  30 Some consequences of these assumptions are:
  31
  32 * That definition is uncommon and queries are very common, we can treat
  33   the property definitions as almost immutable.  Specifically, a query can
  34   never change the state of the definitions.
  35
  36 * That definition is uncommon and needs to be space efficient, it will
  37   be feasible to use a hash table to contain the names (and possibly also
  38   values) of all properties and to reference these instead of duplicating
  39   strings.  Moreover, such a data structure need not be garbage collected.
  40   By converting strings to integers using a structure such as this, string
  41   comparison degenerates to integer comparison.  Additionally, lists of
  42   properties can be sorted by the string index which makes comparisons linear
  43   time rather than quadratic time - the O(n log n) sort cost being amortised.
  44
  45 * A cache for property definitions is also viable, if only implementation
  46   properties are used and not algorithm properties, or at least these are
  47   maintained separately.  This cache would be a hash table, indexed by
  48   the property definition string, and algorithms with the same properties
  49   would share their definition structure.  Again, reducing space use.
  50
  51 * A query cache is desirable.  This would be a hash table keyed by the
  52   algorithm identifier and the entire query string and it would map to
  53   the chosen algorithm.  When a provider is loaded or unloaded, this cache
  54   must be invalidated.  The cache will also be invalidated when the global
  55   properties are changed as doing so removes the need to index on both the
  56   global and requested property strings.
  57
  58 The implementation:
  59
  60 * [property_lock.c](property_lock.c)
  61   contains some wrapper functions to handle the global
  62   lock more easily.  The global lock is held for short periods of time with
  63   per algorithm locking being used for longer intervals.
  64
  65 * [property_string.c](property_string.c)
  66   contains the string cache which converts property
  67   names and values to small integer indices.  Names and values are stored in
  68   separate hash tables.  The two Boolean values, the strings "yes" and "no",
  69   are populated as the first two members of the value table.  All property
  70   names reserved by OpenSSL are also populated here.  No functions are
  71   provided to convert from an index back to the original string (this can be
  72   done by maintaining parallel stacks of strings if required).
  73
  74 * [property_parse.c](property_parse.c)
  75   contains the property definition and query parsers.
  76   These convert ASCII strings into lists of properties.  The resulting
  77   lists are sorted by the name index.  Some additional utility functions
  78   for dealing with property lists are also included: comparison of a query
  79   against a definition and merging two queries into a single larger query.
  80
  81 * [property.c](property.c)
  82   contains the main APIs for defining and using properties.
  83   Algorithms are discovered from their NID and a query string.
  84   The results are cached.
  85
  86   The caching of query results has to be efficient but it must also be robust
  87   against a denial of service attack.  The cache cannot be permitted to grow
  88   without bounds and must garbage collect under-used entries.  The garbage
  89   collection does not have to be exact.
  90
  91 * [defn_cache.c](defn_cache.c)
  92   contains a cache that maps property definition strings to
  93   parsed properties.  It is used by property.c to improve performance when
  94   the same definition appears multiple times.