| 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.
|
|---|
