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