Properties for implementation selection.
authorPauli <paul.dale@oracle.com>
Fri, 16 Nov 2018 01:44:30 +0000 (11:44 +1000)
committerPauli <paul.dale@oracle.com>
Mon, 18 Feb 2019 03:28:14 +0000 (13:28 +1000)
Properties are a sequence of comma separated name=value pairs.  A name
without a corresponding value is assumed to be a Boolean and have the
true value 'yes'.  Values are either strings or numbers.  Strings can be
quoted either _"_ or _'_ or unquoted (with restrictions).  There are no
escape characters inside strings.  Number are either decimal digits or
'0x' followed by hexidecimal digits.  Numbers are represented internally
as signed sixty four bit values.

Queries on properties are a sequence comma separated conditional tests.
These take the form of name=value (equality test), name!=value (inequality
test) or name (Boolean test for truth).  Queries can be parsed, compared
against a definition or merged pairwise.

Reviewed-by: Matt Caswell <matt@openssl.org>
Reviewed-by: Tim Hudson <tjh@openssl.org>
(Merged from https://github.com/openssl/openssl/pull/8224)

25 files changed:
CHANGES
crypto/build.info
crypto/err/err_all.c
crypto/err/openssl.ec
crypto/lhash/lhash.c
crypto/property/README [new file with mode: 0644]
crypto/property/build.info [new file with mode: 0644]
crypto/property/defn_cache.c [new file with mode: 0644]
crypto/property/properties.ebnf [new file with mode: 0644]
crypto/property/properties.xhtml [new file with mode: 0644]
crypto/property/property.c [new file with mode: 0644]
crypto/property/property_lcl.h [new file with mode: 0644]
crypto/property/property_parse.c [new file with mode: 0644]
crypto/property/property_string.c [new file with mode: 0644]
crypto/sparse_array.c
doc/internal/man3/OSSL_METHOD_STORE.pod [new file with mode: 0644]
doc/man3/OPENSSL_LH_COMPFUNC.pod
include/internal/property.h [new file with mode: 0644]
include/openssl/err.h
include/openssl/lhash.h
include/openssl/stack.h
test/build.info
test/property_test.c [new file with mode: 0644]
test/recipes/03-test_property.t [new file with mode: 0644]
test/sparse_array_test.c

diff --git a/CHANGES b/CHANGES
index cca9ed9..5fcf667 100644 (file)
--- a/CHANGES
+++ b/CHANGES
@@ -9,6 +9,10 @@
 
  Changes between 1.1.1 and 3.0.0 [xx XXX xxxx]
 
+  *) Added property based algorithm implementation selection framework to
+     the core.
+     [Paul Dale]
+
   *) Added SCA hardening for modular field inversion in EC_GROUP through
      a new dedicated field_inv() pointer in EC_METHOD.
      This also addresses a leakage affecting conversions from projective
index fc0050e..94ed06e 100644 (file)
@@ -1,7 +1,7 @@
 # Note that these directories are filtered in Configure.  Look for %skipdir
 # there for further explanations.
 SUBDIRS=objects buffer bio stack lhash rand evp asn1 pem x509 x509v3 conf \
-        txt_db pkcs7 pkcs12 ui kdf store \
+        txt_db pkcs7 pkcs12 ui kdf store property \
         md2 md4 md5 sha mdc2 gmac hmac ripemd whrlpool poly1305 blake2 \
         siphash sm3 des aes rc2 rc4 rc5 idea aria bf cast camellia \
         seed sm4 chacha modes bn ec rsa dsa dh sm2 dso engine \
index 3911ecc..4bf020c 100644 (file)
@@ -39,6 +39,7 @@
 #include <openssl/kdferr.h>
 #include <openssl/storeerr.h>
 #include <openssl/esserr.h>
+#include "internal/propertyerr.h"
 
 int err_load_crypto_strings_int(void)
 {
@@ -96,7 +97,8 @@ int err_load_crypto_strings_int(void)
         ERR_load_ASYNC_strings() == 0 ||
 #endif
         ERR_load_KDF_strings() == 0 ||
-        ERR_load_OSSL_STORE_strings() == 0)
+        ERR_load_OSSL_STORE_strings() == 0 ||
+        ERR_load_PROP_strings() == 0)
         return 0;
 
     return 1;
index 94d46d0..901a847 100644 (file)
@@ -35,6 +35,7 @@ L KDF           include/openssl/kdf.h           crypto/kdf/kdf_err.c
 L SM2           crypto/include/internal/sm2.h   crypto/sm2/sm2_err.c
 L OSSL_STORE    include/openssl/store.h         crypto/store/store_err.c
 L ESS           include/openssl/ess.h           crypto/ess/ess_err.c
+L PROP          include/internal/property.h     crypto/property/property_err.c
 
 # additional header files to be scanned for function names
 L NONE          include/openssl/x509_vfy.h      NONE
index c826039..aa0ca1c 100644 (file)
@@ -74,6 +74,16 @@ err:
 }
 
 void OPENSSL_LH_free(OPENSSL_LHASH *lh)
+{
+    if (lh == NULL)
+        return;
+
+    OPENSSL_LH_flush(lh);
+    OPENSSL_free(lh->b);
+    OPENSSL_free(lh);
+}
+
+void OPENSSL_LH_flush(OPENSSL_LHASH *lh)
 {
     unsigned int i;
     OPENSSL_LH_NODE *n, *nn;
@@ -89,8 +99,6 @@ void OPENSSL_LH_free(OPENSSL_LHASH *lh)
             n = nn;
         }
     }
-    OPENSSL_free(lh->b);
-    OPENSSL_free(lh);
 }
 
 void *OPENSSL_LH_insert(OPENSSL_LHASH *lh, void *data)
diff --git a/crypto/property/README b/crypto/property/README
new file mode 100644 (file)
index 0000000..b3f56cf
--- /dev/null
@@ -0,0 +1,87 @@
+Properties are associated with algorithms and are used to select between different implementations dynamically.
+
+This implementation is based on a number of assumptions:
+
+* Property definition is uncommon.  I.e. providers will be loaded and
+  unloaded relatively infrequently, if at all.
+
+* The number of distinct property names will be small.
+
+* Providers will often give the same implementation properties to most or
+  all of their implemented algorithms.  E.g. the FIPS property would be set
+  across an entire provider.  Likewise for, hardware, accelerated, software,
+  HSM and, perhaps, constant_time.
+
+* There are a lot of algorithm implementations, therefore property
+  definitions should be space efficient.  However...
+
+* ... property queries are very common.  These must be fast.
+
+* Property queries come from a small set and are reused many times typically.
+  I.e. an application tends to use the same set of queries over and over,
+  rather than spanning a wide variety of queries.
+
+* Property queries can never add new property definitions.
+
+
+Some consequences of these assumptions are:
+
+* That definition is uncommon and queries are very common, we can treat
+  the property definitions as almost immutable.  Specifically, a query can
+  never change the state of the definitions.
+
+* That definition is uncommon and needs to be space efficient, it will
+  be feasible to use a hash table to contain the names (and possibly also
+  values) of all properties and to reference these instead of duplicating
+  strings.  Moreover, such a data structure need not be garbage collected.
+  By converting strings to integers using a structure such as this, string
+  comparison degenerates to integer comparison.  Additionally, lists of
+  properties can be sorted by the string index which makes comparisons linear
+  time rather than quadratic time - the O(n log n) sort cost being amortised.
+
+* A cache for property definitions is also viable, if only implementation
+  properties are used and not algorithm properties, or at least these are
+  maintained separately.  This cache would be a hash table, indexed by
+  the property definition string, and algorithms with the same properties
+  would share their definition structure.  Again, reducing space use.
+
+* A query cache is desirable.  This would be a hash table keyed by the
+  algorithm identifier and the entire query string and it would map to
+  the chosen algorithm.  When a provider is loaded or unloaded, this cache
+  must be invalidated.  The cache will also be invalidated when the global
+  properties are changed as doing so removes the need to index on both the
+  global and requested property strings.
+
+
+The implementation:
+
+* property_lock.c contains some wrapper functions to handle the global
+  lock more easily.  The global lock is held for short periods of time with
+  per algorithm locking being used for longer intervals.
+
+* property_string.c contains the string cache which converts property
+  names and values to small integer indices.  Names and values are stored in
+  separate hash tables.  The two Boolean values, the strings "yes" and "no",
+  are populated as the first two members of the value table.  All property
+  names reserved by OpenSSL are also populated here.  No functions are
+  provided to convert from an index back to the original string (this can be
+  done by maintaining parallel stacks of strings if required).
+
+* property_parse.c contains the property definition and query parsers.
+  These convert ASCII strings into lists of properties.  The resulting
+  lists are sorted by the name index.  Some additional utility functions
+  for dealing with property lists are also included: comparison of a query
+  against a definition and merging two queries into a single larger query.
+
+* property.c contains the main APIs for defining and using properties.
+  Algorithms are discovered from their NID and a query string.
+  The results are cached.
+
+  The caching of query results has to be efficient but it must also be robust
+  against a denial of service attack.  The cache cannot be permitted to grow
+  without bounds and must garbage collect under-used entries.  The garbage
+  collection does not have to be exact.
+
+* defn_cache.c contains a cache that maps property definition strings to
+  parsed properties.  It is used by property.c to improve performance when
+  the same definition appears multiple times.
diff --git a/crypto/property/build.info b/crypto/property/build.info
new file mode 100644 (file)
index 0000000..3a86b6e
--- /dev/null
@@ -0,0 +1,3 @@
+LIBS=../../libcrypto
+SOURCE[../../libcrypto]=property_string.c property_parse.c property.c \
+                        property_err.c defn_cache.c
diff --git a/crypto/property/defn_cache.c b/crypto/property/defn_cache.c
new file mode 100644 (file)
index 0000000..df87c19
--- /dev/null
@@ -0,0 +1,105 @@
+/*
+ * Copyright 2019 The OpenSSL Project Authors. All Rights Reserved.
+ * Copyright (c) 2019, Oracle and/or its affiliates.  All rights reserved.
+ *
+ * Licensed under the Apache License 2.0 (the "License").  You may not use
+ * this file except in compliance with the License.  You can obtain a copy
+ * in the file LICENSE in the source distribution or at
+ * https://www.openssl.org/source/license.html
+ */
+
+#include <string.h>
+#include <openssl/err.h>
+#include <openssl/lhash.h>
+#include "internal/propertyerr.h"
+#include "internal/property.h"
+#include "property_lcl.h"
+
+/*
+ * Implement a property definition cache.
+ * These functions assume that they are called under a write lock.
+ * No attempt is made to clean out the cache, except when it is shut down.
+ */
+
+typedef struct {
+    const char *prop;
+    OSSL_PROPERTY_LIST *defn;
+    char body[1];
+} PROPERTY_DEFN_ELEM;
+
+DEFINE_LHASH_OF(PROPERTY_DEFN_ELEM);
+
+static LHASH_OF(PROPERTY_DEFN_ELEM) *property_defns = NULL;
+
+static unsigned long property_defn_hash(const PROPERTY_DEFN_ELEM *a)
+{
+    return OPENSSL_LH_strhash(a->prop);
+}
+
+static int property_defn_cmp(const PROPERTY_DEFN_ELEM *a,
+                             const PROPERTY_DEFN_ELEM *b)
+{
+    return strcmp(a->prop, b->prop);
+}
+
+static void property_defn_free(PROPERTY_DEFN_ELEM *elem)
+{
+    ossl_property_free(elem->defn);
+    OPENSSL_free(elem);
+}
+
+int ossl_prop_defn_init(void)
+{
+    property_defns = lh_PROPERTY_DEFN_ELEM_new(&property_defn_hash,
+                                               &property_defn_cmp);
+    return property_defns != NULL;
+}
+
+void ossl_prop_defn_cleanup(void)
+{
+    if (property_defns != NULL) {
+        lh_PROPERTY_DEFN_ELEM_doall(property_defns, &property_defn_free);
+        lh_PROPERTY_DEFN_ELEM_free(property_defns);
+        property_defns = NULL;
+    }
+}
+
+OSSL_PROPERTY_LIST *ossl_prop_defn_get(const char *prop)
+{
+    PROPERTY_DEFN_ELEM elem, *r;
+
+    elem.prop = prop;
+    r = lh_PROPERTY_DEFN_ELEM_retrieve(property_defns, &elem);
+    return r != NULL ? r->defn : NULL;
+}
+
+int ossl_prop_defn_set(const char *prop, OSSL_PROPERTY_LIST *pl)
+{
+    PROPERTY_DEFN_ELEM elem, *old, *p = NULL;
+    size_t len;
+
+    if (prop == NULL)
+        return 1;
+
+    if (pl == NULL) {
+        elem.prop = prop;
+        lh_PROPERTY_DEFN_ELEM_delete(property_defns, &elem);
+        return 1;
+    }
+    len = strlen(prop);
+    p = OPENSSL_malloc(sizeof(*p) + len);
+    if (p != NULL) {
+        p->prop = p->body;
+        p->defn = pl;
+        memcpy(p->body, prop, len + 1);
+        old = lh_PROPERTY_DEFN_ELEM_insert(property_defns, p);
+        if (old != NULL) {
+            property_defn_free(old);
+            return 1;
+        }
+        if (!lh_PROPERTY_DEFN_ELEM_error(property_defns))
+            return 1;
+    }
+    OPENSSL_free(p);
+    return 0;
+}
diff --git a/crypto/property/properties.ebnf b/crypto/property/properties.ebnf
new file mode 100644 (file)
index 0000000..9a6857f
--- /dev/null
@@ -0,0 +1,17 @@
+(* https://bottlecaps.de/rr/ui *)
+
+Definition
+      ::= PropertyName ( '=' Value )? ( ',' PropertyName ( '=' Value )? )*
+Query ::= ( '-'? PropertyName | PropertyName ( '=' | '!=' ) Value )
+          ( ',' ( '-'? PropertyName | PropertyName ( '=' | '!=' ) Value ) )*
+Value    ::= NumberLiteral
+        | StringLiteral
+StringLiteral ::= QuotedString | UnquotedString
+QuotedString     ::= '"' [^"]* '"'
+       | "'" [^']* "'"
+UnquotedString ::= [^{space},]+
+NumberLiteral
+     ::= '0' ( [0-7]* | 'x' [0-9A-Fa-f]+ )
+       | '-'? [1-9] [0-9]+
+PropertyName
+         ::= [A-Z] [A-Z0-9_]* ( '.' [A-Z] [A-Z0-9_]* )*
diff --git a/crypto/property/properties.xhtml b/crypto/property/properties.xhtml
new file mode 100644 (file)
index 0000000..3382722
--- /dev/null
@@ -0,0 +1,685 @@
+<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
+<html xmlns="http://www.w3.org/1999/xhtml">
+   <head>
+      <meta http-equiv="Content-Type" content="application/xhtml+xml; charset=UTF-8" />
+      <meta name="generator" content="Railroad Diagram Generator 1.56.1774" />
+      <style type="text/css">
+    ::-moz-selection
+    {
+      color: #FFFCF0;
+      background: #0F0C00;
+    }
+    ::selection
+    {
+      color: #FFFCF0;
+      background: #0F0C00;
+    }      
+    .ebnf a, .grammar a
+    {
+      text-decoration: none;
+    }
+    .ebnf a:hover, .grammar a:hover
+    {
+      color: #050400;
+      text-decoration: underline;
+    }    
+    .signature
+    {
+      color: #806600;
+      font-size: 11px;
+      text-align: right;
+    }
+    body
+    {
+      font: normal 12px Verdana, sans-serif;
+      color: #0F0C00;
+      background: #FFFCF0;
+    }
+    a:link, a:visited
+    {
+      color: #0F0C00;
+    }
+    a:link.signature, a:visited.signature
+    {
+      color: #806600;
+    }
+    a.button, #tabs li a
+    {
+      padding: 0.25em 0.5em;
+      border: 1px solid #806600;
+      background: #F1E8C6;
+      color: #806600;
+      text-decoration: none;
+      font-weight: bold;
+    }
+    a.button:hover, #tabs li a:hover
+    {
+      color: #050400;
+      background: #FFF6D1;
+      border-color: #050400;       
+    }     
+    #tabs
+    {
+      padding: 3px 10px;
+      margin-left: 0;
+      margin-top: 58px;
+      border-bottom: 1px solid #0F0C00;
+    }  
+    #tabs li
+    {
+      list-style: none;
+      margin-left: 5px;
+      display: inline;
+    }
+    #tabs li a
+    {     
+      border-bottom: 1px solid #0F0C00;
+    }
+    #tabs li a.active
+    {
+      color: #0F0C00;
+      background: #FFFCF0;
+      border-color: #0F0C00;
+      border-bottom: 1px solid #FFFCF0;
+      outline: none;
+    }
+    #divs div
+    {
+      display: none;
+      overflow:auto;
+    }
+    #divs div.active
+    {
+      display: block;
+    }
+    #text
+    {
+      border-color: #806600;
+      background: #FFFEFA;
+      color: #050400;
+    }
+    .small
+    {
+      vertical-align: top;
+      text-align: right;
+      font-size: 9px;
+      font-weight: normal;
+      line-height: 120%;
+    }
+    td.small
+    {
+      padding-top: 0px;
+    }
+    .hidden
+    {
+      visibility: hidden;
+    }
+    td:hover .hidden 
+    {
+      visibility: visible;
+    }
+    div.download
+    {
+      display: none;
+      background: #FFFCF0;
+      position: absolute;
+      right: 34px;
+      top: 94px;
+      padding: 10px;
+      border: 1px dotted #0F0C00;
+    }
+    #divs div.ebnf, .ebnf code
+    {
+      display: block;
+      padding: 10px;
+      background: #FFF6D1;
+      width: 1000px;
+    }
+    #divs div.grammar
+    {
+      display: block;
+      padding-left: 16px;
+      padding-top: 2px;
+      padding-bottom: 2px;
+      background: #FFF6D1;
+    }
+    pre
+    {
+      margin: 0px;
+    }
+    .ebnf div
+    {
+      padding-left: 13ch;
+      text-indent: -13ch;
+    }
+    .ebnf code, .grammar code, textarea, pre
+    {
+      font:12px SFMono-Regular,Consolas,Liberation Mono,Menlo,Courier,monospace;
+    }
+    tr.option-line td:first-child
+    {
+      text-align: right
+    }
+    tr.option-text td
+    {
+      padding-bottom: 10px
+    }
+    table.palette
+    {
+      border-top: 1px solid #050400;
+      border-right: 1px solid #050400;
+      margin-bottom: 4px
+    }
+    td.palette
+    {
+      border-bottom: 1px solid #050400;
+      border-left: 1px solid #050400;
+    }
+    a.palette
+    {
+      padding: 2px 3px 2px 10px;
+      text-decoration: none;
+    }
+    .palette
+    {
+      -webkit-user-select: none;
+      -khtml-user-select: none;
+      -moz-user-select: none;
+      -o-user-select: none;
+      -ms-user-select: none;
+    }
+  </style><svg xmlns="http://www.w3.org/2000/svg">
+         <defs>
+            <style type="text/css">
+    @namespace "http://www.w3.org/2000/svg";
+    .line                 {fill: none; stroke: #332900;}
+    .bold-line            {stroke: #141000; shape-rendering: crispEdges; stroke-width: 2; }
+    .thin-line            {stroke: #1F1800; shape-rendering: crispEdges}
+    .filled               {fill: #332900; stroke: none;}
+    text.terminal         {font-family: Verdana, Sans-serif;
+                            font-size: 12px;
+                            fill: #141000;
+                            font-weight: bold;
+                          }
+    text.nonterminal      {font-family: Verdana, Sans-serif;
+                            font-size: 12px;
+                            fill: #1A1400;
+                            font-weight: normal;
+                          }
+    text.regexp           {font-family: Verdana, Sans-serif;
+                            font-size: 12px;
+                            fill: #1F1800;
+                            font-weight: normal;
+                          }
+    rect, circle, polygon {fill: #332900; stroke: #332900;}
+    rect.terminal         {fill: #FFDB4D; stroke: #332900;}
+    rect.nonterminal      {fill: #FFEC9E; stroke: #332900;}
+    rect.text             {fill: none; stroke: none;}    
+    polygon.regexp        {fill: #FFF4C7; stroke: #332900;}
+  </style>
+         </defs></svg></head>
+   <body>
+      <xhtml:p xmlns:xhtml="http://www.w3.org/1999/xhtml" style="font-size: 14px; font-weight:bold"><xhtml:a name="Definition">Definition:</xhtml:a></xhtml:p><svg xmlns="http://www.w3.org/2000/svg" width="375" height="113">
+         <defs>
+            <style type="text/css">
+    @namespace "http://www.w3.org/2000/svg";
+    .line                 {fill: none; stroke: #332900;}
+    .bold-line            {stroke: #141000; shape-rendering: crispEdges; stroke-width: 2; }
+    .thin-line            {stroke: #1F1800; shape-rendering: crispEdges}
+    .filled               {fill: #332900; stroke: none;}
+    text.terminal         {font-family: Verdana, Sans-serif;
+                            font-size: 12px;
+                            fill: #141000;
+                            font-weight: bold;
+                          }
+    text.nonterminal      {font-family: Verdana, Sans-serif;
+                            font-size: 12px;
+                            fill: #1A1400;
+                            font-weight: normal;
+                          }
+    text.regexp           {font-family: Verdana, Sans-serif;
+                            font-size: 12px;
+                            fill: #1F1800;
+                            font-weight: normal;
+                          }
+    rect, circle, polygon {fill: #332900; stroke: #332900;}
+    rect.terminal         {fill: #FFDB4D; stroke: #332900;}
+    rect.nonterminal      {fill: #FFEC9E; stroke: #332900;}
+    rect.text             {fill: none; stroke: none;}    
+    polygon.regexp        {fill: #FFF4C7; stroke: #332900;}
+  </style>
+         </defs>
+         <polygon points="9 61 1 57 1 65"/>
+         <polygon points="17 61 9 57 9 65"/><a xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="#PropertyName" xlink:title="PropertyName">
+            <rect x="51" y="47" width="110" height="32"/>
+            <rect x="49" y="45" width="110" height="32" class="nonterminal"/>
+            <text class="nonterminal" x="59" y="65">PropertyName</text></a><rect x="201" y="79" width="30" height="32" rx="10"/>
+         <rect x="199" y="77" width="30" height="32" class="terminal" rx="10"/>
+         <text class="terminal" x="209" y="97">=</text><a xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="#Value" xlink:title="Value">
+            <rect x="251" y="79" width="56" height="32"/>
+            <rect x="249" y="77" width="56" height="32" class="nonterminal"/>
+            <text class="nonterminal" x="259" y="97">Value</text></a><rect x="51" y="3" width="24" height="32" rx="10"/>
+         <rect x="49" y="1" width="24" height="32" class="terminal" rx="10"/>
+         <text class="terminal" x="59" y="21">,</text>
+         <svg:path xmlns:svg="http://www.w3.org/2000/svg" class="line" d="m17 61 h2 m20 0 h10 m110 0 h10 m20 0 h10 m0 0 h116 m-146 0 h20 m126 0 h20 m-166 0 q10 0 10 10 m146 0 q0 -10 10 -10 m-156 10 v12 m146 0 v-12 m-146 12 q0 10 10 10 m126 0 q10 0 10 -10 m-136 10 h10 m30 0 h10 m0 0 h10 m56 0 h10 m-296 -32 l20 0 m-1 0 q-9 0 -9 -10 l0 -24 q0 -10 10 -10 m296 44 l20 0 m-20 0 q10 0 10 -10 l0 -24 q0 -10 -10 -10 m-296 0 h10 m24 0 h10 m0 0 h252 m23 44 h-3"/>
+         <polygon points="365 61 373 57 373 65"/>
+         <polygon points="365 61 357 57 357 65"/></svg><xhtml:p xmlns:xhtml="http://www.w3.org/1999/xhtml">
+         <xhtml:div class="ebnf"><xhtml:code>
+               <div><a href="#Definition" title="Definition">Definition</a></div>
+               <div>         ::= <a href="#PropertyName" title="PropertyName">PropertyName</a> ( '=' <a href="#Value" title="Value">Value</a> )? ( ',' <a href="#PropertyName" title="PropertyName">PropertyName</a> ( '=' <a href="#Value" title="Value">Value</a> )? )*</div></xhtml:code></xhtml:div>
+      </xhtml:p>
+      <xhtml:p xmlns:xhtml="http://www.w3.org/1999/xhtml">no references</xhtml:p><xhtml:br xmlns:xhtml="http://www.w3.org/1999/xhtml" /><xhtml:p xmlns:xhtml="http://www.w3.org/1999/xhtml" style="font-size: 14px; font-weight:bold"><xhtml:a name="Query">Query:</xhtml:a></xhtml:p><svg xmlns="http://www.w3.org/2000/svg" width="419" height="201">
+         <defs>
+            <style type="text/css">
+    @namespace "http://www.w3.org/2000/svg";
+    .line                 {fill: none; stroke: #332900;}
+    .bold-line            {stroke: #141000; shape-rendering: crispEdges; stroke-width: 2; }
+    .thin-line            {stroke: #1F1800; shape-rendering: crispEdges}
+    .filled               {fill: #332900; stroke: none;}
+    text.terminal         {font-family: Verdana, Sans-serif;
+                            font-size: 12px;
+                            fill: #141000;
+                            font-weight: bold;
+                          }
+    text.nonterminal      {font-family: Verdana, Sans-serif;
+                            font-size: 12px;
+                            fill: #1A1400;
+                            font-weight: normal;
+                          }
+    text.regexp           {font-family: Verdana, Sans-serif;
+                            font-size: 12px;
+                            fill: #1F1800;
+                            font-weight: normal;
+                          }
+    rect, circle, polygon {fill: #332900; stroke: #332900;}
+    rect.terminal         {fill: #FFDB4D; stroke: #332900;}
+    rect.nonterminal      {fill: #FFEC9E; stroke: #332900;}
+    rect.text             {fill: none; stroke: none;}    
+    polygon.regexp        {fill: #FFF4C7; stroke: #332900;}
+  </style>
+         </defs>
+         <polygon points="9 61 1 57 1 65"/>
+         <polygon points="17 61 9 57 9 65"/>
+         <rect x="91" y="79" width="26" height="32" rx="10"/>
+         <rect x="89" y="77" width="26" height="32" class="terminal" rx="10"/>
+         <text class="terminal" x="99" y="97">-</text><a xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="#PropertyName" xlink:title="PropertyName">
+            <rect x="157" y="47" width="110" height="32"/>
+            <rect x="155" y="45" width="110" height="32" class="nonterminal"/>
+            <text class="nonterminal" x="165" y="65">PropertyName</text></a><a xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="#PropertyName" xlink:title="PropertyName">
+            <rect x="71" y="123" width="110" height="32"/>
+            <rect x="69" y="121" width="110" height="32" class="nonterminal"/>
+            <text class="nonterminal" x="79" y="141">PropertyName</text></a><rect x="221" y="123" width="30" height="32" rx="10"/>
+         <rect x="219" y="121" width="30" height="32" class="terminal" rx="10"/>
+         <text class="terminal" x="229" y="141">=</text>
+         <rect x="221" y="167" width="34" height="32" rx="10"/>
+         <rect x="219" y="165" width="34" height="32" class="terminal" rx="10"/>
+         <text class="terminal" x="229" y="185">!=</text><a xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="#Value" xlink:title="Value">
+            <rect x="295" y="123" width="56" height="32"/>
+            <rect x="293" y="121" width="56" height="32" class="nonterminal"/>
+            <text class="nonterminal" x="303" y="141">Value</text></a><rect x="51" y="3" width="24" height="32" rx="10"/>
+         <rect x="49" y="1" width="24" height="32" class="terminal" rx="10"/>
+         <text class="terminal" x="59" y="21">,</text>
+         <svg:path xmlns:svg="http://www.w3.org/2000/svg" class="line" d="m17 61 h2 m60 0 h10 m0 0 h36 m-66 0 h20 m46 0 h20 m-86 0 q10 0 10 10 m66 0 q0 -10 10 -10 m-76 10 v12 m66 0 v-12 m-66 12 q0 10 10 10 m46 0 q10 0 10 -10 m-56 10 h10 m26 0 h10 m20 -32 h10 m110 0 h10 m0 0 h84 m-320 0 h20 m300 0 h20 m-340 0 q10 0 10 10 m320 0 q0 -10 10 -10 m-330 10 v56 m320 0 v-56 m-320 56 q0 10 10 10 m300 0 q10 0 10 -10 m-310 10 h10 m110 0 h10 m20 0 h10 m30 0 h10 m0 0 h4 m-74 0 h20 m54 0 h20 m-94 0 q10 0 10 10 m74 0 q0 -10 10 -10 m-84 10 v24 m74 0 v-24 m-74 24 q0 10 10 10 m54 0 q10 0 10 -10 m-64 10 h10 m34 0 h10 m20 -44 h10 m56 0 h10 m-340 -76 l20 0 m-1 0 q-9 0 -9 -10 l0 -24 q0 -10 10 -10 m340 44 l20 0 m-20 0 q10 0 10 -10 l0 -24 q0 -10 -10 -10 m-340 0 h10 m24 0 h10 m0 0 h296 m23 44 h-3"/>
+         <polygon points="409 61 417 57 417 65"/>
+         <polygon points="409 61 401 57 401 65"/></svg><xhtml:p xmlns:xhtml="http://www.w3.org/1999/xhtml">
+         <xhtml:div class="ebnf"><xhtml:code>
+               <div><a href="#Query" title="Query">Query</a>    ::= ( '-'? <a href="#PropertyName" title="PropertyName">PropertyName</a> | <a href="#PropertyName" title="PropertyName">PropertyName</a> ( '=' | '!=' ) <a href="#Value" title="Value">Value</a> ) ( ',' ( '-'? <a href="#PropertyName" title="PropertyName">PropertyName</a> | <a href="#PropertyName" title="PropertyName">PropertyName</a> ( '=' | '!=' ) <a href="#Value" title="Value">Value</a> ) )*</div></xhtml:code></xhtml:div>
+      </xhtml:p>
+      <xhtml:p xmlns:xhtml="http://www.w3.org/1999/xhtml">no references</xhtml:p><xhtml:br xmlns:xhtml="http://www.w3.org/1999/xhtml" /><xhtml:p xmlns:xhtml="http://www.w3.org/1999/xhtml" style="font-size: 14px; font-weight:bold"><xhtml:a name="Value">Value:</xhtml:a></xhtml:p><svg xmlns="http://www.w3.org/2000/svg" width="207" height="81">
+         <defs>
+            <style type="text/css">
+    @namespace "http://www.w3.org/2000/svg";
+    .line                 {fill: none; stroke: #332900;}
+    .bold-line            {stroke: #141000; shape-rendering: crispEdges; stroke-width: 2; }
+    .thin-line            {stroke: #1F1800; shape-rendering: crispEdges}
+    .filled               {fill: #332900; stroke: none;}
+    text.terminal         {font-family: Verdana, Sans-serif;
+                            font-size: 12px;
+                            fill: #141000;
+                            font-weight: bold;
+                          }
+    text.nonterminal      {font-family: Verdana, Sans-serif;
+                            font-size: 12px;
+                            fill: #1A1400;
+                            font-weight: normal;
+                          }
+    text.regexp           {font-family: Verdana, Sans-serif;
+                            font-size: 12px;
+                            fill: #1F1800;
+                            font-weight: normal;
+                          }
+    rect, circle, polygon {fill: #332900; stroke: #332900;}
+    rect.terminal         {fill: #FFDB4D; stroke: #332900;}
+    rect.nonterminal      {fill: #FFEC9E; stroke: #332900;}
+    rect.text             {fill: none; stroke: none;}    
+    polygon.regexp        {fill: #FFF4C7; stroke: #332900;}
+  </style>
+         </defs>
+         <polygon points="9 17 1 13 1 21"/>
+         <polygon points="17 17 9 13 9 21"/><a xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="#NumberLiteral" xlink:title="NumberLiteral">
+            <rect x="51" y="3" width="108" height="32"/>
+            <rect x="49" y="1" width="108" height="32" class="nonterminal"/>
+            <text class="nonterminal" x="59" y="21">NumberLiteral</text></a><a xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="#StringLiteral" xlink:title="StringLiteral">
+            <rect x="51" y="47" width="96" height="32"/>
+            <rect x="49" y="45" width="96" height="32" class="nonterminal"/>
+            <text class="nonterminal" x="59" y="65">StringLiteral</text></a><svg:path xmlns:svg="http://www.w3.org/2000/svg" class="line" d="m17 17 h2 m20 0 h10 m108 0 h10 m-148 0 h20 m128 0 h20 m-168 0 q10 0 10 10 m148 0 q0 -10 10 -10 m-158 10 v24 m148 0 v-24 m-148 24 q0 10 10 10 m128 0 q10 0 10 -10 m-138 10 h10 m96 0 h10 m0 0 h12 m23 -44 h-3"/>
+         <polygon points="197 17 205 13 205 21"/>
+         <polygon points="197 17 189 13 189 21"/></svg><xhtml:p xmlns:xhtml="http://www.w3.org/1999/xhtml">
+         <xhtml:div class="ebnf"><xhtml:code>
+               <div><a href="#Value" title="Value">Value</a>    ::= <a href="#NumberLiteral" title="NumberLiteral">NumberLiteral</a></div>
+               <div>           | <a href="#StringLiteral" title="StringLiteral">StringLiteral</a></div></xhtml:code></xhtml:div>
+      </xhtml:p>
+      <xhtml:p xmlns:xhtml="http://www.w3.org/1999/xhtml">referenced by:
+         <xhtml:ul>
+            <xhtml:li><xhtml:a href="#Definition" title="Definition">Definition</xhtml:a></xhtml:li>
+            <xhtml:li><xhtml:a href="#Query" title="Query">Query</xhtml:a></xhtml:li>
+         </xhtml:ul>
+      </xhtml:p><xhtml:br xmlns:xhtml="http://www.w3.org/1999/xhtml" /><xhtml:p xmlns:xhtml="http://www.w3.org/1999/xhtml" style="font-size: 14px; font-weight:bold"><xhtml:a name="StringLiteral">StringLiteral:</xhtml:a></xhtml:p><svg xmlns="http://www.w3.org/2000/svg" width="219" height="81">
+         <defs>
+            <style type="text/css">
+    @namespace "http://www.w3.org/2000/svg";
+    .line                 {fill: none; stroke: #332900;}
+    .bold-line            {stroke: #141000; shape-rendering: crispEdges; stroke-width: 2; }
+    .thin-line            {stroke: #1F1800; shape-rendering: crispEdges}
+    .filled               {fill: #332900; stroke: none;}
+    text.terminal         {font-family: Verdana, Sans-serif;
+                            font-size: 12px;
+                            fill: #141000;
+                            font-weight: bold;
+                          }
+    text.nonterminal      {font-family: Verdana, Sans-serif;
+                            font-size: 12px;
+                            fill: #1A1400;
+                            font-weight: normal;
+                          }
+    text.regexp           {font-family: Verdana, Sans-serif;
+                            font-size: 12px;
+                            fill: #1F1800;
+                            font-weight: normal;
+                          }
+    rect, circle, polygon {fill: #332900; stroke: #332900;}
+    rect.terminal         {fill: #FFDB4D; stroke: #332900;}
+    rect.nonterminal      {fill: #FFEC9E; stroke: #332900;}
+    rect.text             {fill: none; stroke: none;}    
+    polygon.regexp        {fill: #FFF4C7; stroke: #332900;}
+  </style>
+         </defs>
+         <polygon points="9 17 1 13 1 21"/>
+         <polygon points="17 17 9 13 9 21"/><a xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="#QuotedString" xlink:title="QuotedString">
+            <rect x="51" y="3" width="104" height="32"/>
+            <rect x="49" y="1" width="104" height="32" class="nonterminal"/>
+            <text class="nonterminal" x="59" y="21">QuotedString</text></a><a xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="#UnquotedString" xlink:title="UnquotedString">
+            <rect x="51" y="47" width="120" height="32"/>
+            <rect x="49" y="45" width="120" height="32" class="nonterminal"/>
+            <text class="nonterminal" x="59" y="65">UnquotedString</text></a><svg:path xmlns:svg="http://www.w3.org/2000/svg" class="line" d="m17 17 h2 m20 0 h10 m104 0 h10 m0 0 h16 m-160 0 h20 m140 0 h20 m-180 0 q10 0 10 10 m160 0 q0 -10 10 -10 m-170 10 v24 m160 0 v-24 m-160 24 q0 10 10 10 m140 0 q10 0 10 -10 m-150 10 h10 m120 0 h10 m23 -44 h-3"/>
+         <polygon points="209 17 217 13 217 21"/>
+         <polygon points="209 17 201 13 201 21"/></svg><xhtml:p xmlns:xhtml="http://www.w3.org/1999/xhtml">
+         <xhtml:div class="ebnf"><xhtml:code>
+               <div><a href="#StringLiteral" title="StringLiteral">StringLiteral</a></div>
+               <div>         ::= <a href="#QuotedString" title="QuotedString">QuotedString</a></div>
+               <div>           | <a href="#UnquotedString" title="UnquotedString">UnquotedString</a></div></xhtml:code></xhtml:div>
+      </xhtml:p>
+      <xhtml:p xmlns:xhtml="http://www.w3.org/1999/xhtml">referenced by:
+         <xhtml:ul>
+            <xhtml:li><xhtml:a href="#Value" title="Value">Value</xhtml:a></xhtml:li>
+         </xhtml:ul>
+      </xhtml:p><xhtml:br xmlns:xhtml="http://www.w3.org/1999/xhtml" /><xhtml:p xmlns:xhtml="http://www.w3.org/1999/xhtml" style="font-size: 14px; font-weight:bold"><xhtml:a name="QuotedString">QuotedString:</xhtml:a></xhtml:p><svg xmlns="http://www.w3.org/2000/svg" width="327" height="151">
+         <defs>
+            <style type="text/css">
+    @namespace "http://www.w3.org/2000/svg";
+    .line                 {fill: none; stroke: #332900;}
+    .bold-line            {stroke: #141000; shape-rendering: crispEdges; stroke-width: 2; }
+    .thin-line            {stroke: #1F1800; shape-rendering: crispEdges}
+    .filled               {fill: #332900; stroke: none;}
+    text.terminal         {font-family: Verdana, Sans-serif;
+                            font-size: 12px;
+                            fill: #141000;
+                            font-weight: bold;
+                          }
+    text.nonterminal      {font-family: Verdana, Sans-serif;
+                            font-size: 12px;
+                            fill: #1A1400;
+                            font-weight: normal;
+                          }
+    text.regexp           {font-family: Verdana, Sans-serif;
+                            font-size: 12px;
+                            fill: #1F1800;
+                            font-weight: normal;
+                          }
+    rect, circle, polygon {fill: #332900; stroke: #332900;}
+    rect.terminal         {fill: #FFDB4D; stroke: #332900;}
+    rect.nonterminal      {fill: #FFEC9E; stroke: #332900;}
+    rect.text             {fill: none; stroke: none;}    
+    polygon.regexp        {fill: #FFF4C7; stroke: #332900;}
+  </style>
+         </defs>
+         <polygon points="9 33 1 29 1 37"/>
+         <polygon points="17 33 9 29 9 37"/>
+         <rect x="51" y="19" width="26" height="32" rx="10"/>
+         <rect x="49" y="17" width="26" height="32" class="terminal" rx="10"/>
+         <text class="terminal" x="59" y="37">"</text>
+         <polygon points="137 35 144 19 186 19 193 35 186 51 144 51"/>
+         <polygon points="135 33 142 17 184 17 191 33 184 49 142 49" class="regexp"/>
+         <text class="regexp" x="150" y="37">[^"]</text>
+         <rect x="253" y="19" width="26" height="32" rx="10"/>
+         <rect x="251" y="17" width="26" height="32" class="terminal" rx="10"/>
+         <text class="terminal" x="261" y="37">"</text>
+         <rect x="51" y="101" width="24" height="32" rx="10"/>
+         <rect x="49" y="99" width="24" height="32" class="terminal" rx="10"/>
+         <text class="terminal" x="59" y="119">'</text>
+         <polygon points="135 117 142 101 182 101 189 117 182 133 142 133"/>
+         <polygon points="133 115 140 99 180 99 187 115 180 131 140 131" class="regexp"/>
+         <text class="regexp" x="148" y="119">[^']</text>
+         <rect x="249" y="101" width="24" height="32" rx="10"/>
+         <rect x="247" y="99" width="24" height="32" class="terminal" rx="10"/>
+         <text class="terminal" x="257" y="119">'</text>
+         <svg:path xmlns:svg="http://www.w3.org/2000/svg" class="line" d="m17 33 h2 m20 0 h10 m26 0 h10 m40 0 h10 m56 0 h10 m-96 0 l20 0 m-1 0 q-9 0 -9 -10 l0 -12 q0 -10 10 -10 m76 32 l20 0 m-20 0 q10 0 10 -10 l0 -12 q0 -10 -10 -10 m-76 0 h10 m0 0 h66 m-116 32 h20 m116 0 h20 m-156 0 q10 0 10 10 m136 0 q0 -10 10 -10 m-146 10 v14 m136 0 v-14 m-136 14 q0 10 10 10 m116 0 q10 0 10 -10 m-126 10 h10 m0 0 h106 m20 -34 h10 m26 0 h10 m-268 0 h20 m248 0 h20 m-288 0 q10 0 10 10 m268 0 q0 -10 10 -10 m-278 10 v62 m268 0 v-62 m-268 62 q0 10 10 10 m248 0 q10 0 10 -10 m-258 10 h10 m24 0 h10 m40 0 h10 m54 0 h10 m-94 0 l20 0 m-1 0 q-9 0 -9 -10 l0 -12 q0 -10 10 -10 m74 32 l20 0 m-20 0 q10 0 10 -10 l0 -12 q0 -10 -10 -10 m-74 0 h10 m0 0 h64 m-114 32 h20 m114 0 h20 m-154 0 q10 0 10 10 m134 0 q0 -10 10 -10 m-144 10 v14 m134 0 v-14 m-134 14 q0 10 10 10 m114 0 q10 0 10 -10 m-124 10 h10 m0 0 h104 m20 -34 h10 m24 0 h10 m0 0 h6 m23 -82 h-3"/>
+         <polygon points="317 33 325 29 325 37"/>
+         <polygon points="317 33 309 29 309 37"/></svg><xhtml:p xmlns:xhtml="http://www.w3.org/1999/xhtml">
+         <xhtml:div class="ebnf"><xhtml:code>
+               <div><a href="#QuotedString" title="QuotedString">QuotedString</a></div>
+               <div>         ::= '"' [^"]* '"'</div>
+               <div>           | "'" [^']* "'"</div></xhtml:code></xhtml:div>
+      </xhtml:p>
+      <xhtml:p xmlns:xhtml="http://www.w3.org/1999/xhtml">referenced by:
+         <xhtml:ul>
+            <xhtml:li><xhtml:a href="#StringLiteral" title="StringLiteral">StringLiteral</xhtml:a></xhtml:li>
+         </xhtml:ul>
+      </xhtml:p><xhtml:br xmlns:xhtml="http://www.w3.org/1999/xhtml" /><xhtml:p xmlns:xhtml="http://www.w3.org/1999/xhtml" style="font-size: 14px; font-weight:bold"><xhtml:a name="UnquotedString">UnquotedString:</xhtml:a></xhtml:p><svg xmlns="http://www.w3.org/2000/svg" width="207" height="53">
+         <defs>
+            <style type="text/css">
+    @namespace "http://www.w3.org/2000/svg";
+    .line                 {fill: none; stroke: #332900;}
+    .bold-line            {stroke: #141000; shape-rendering: crispEdges; stroke-width: 2; }
+    .thin-line            {stroke: #1F1800; shape-rendering: crispEdges}
+    .filled               {fill: #332900; stroke: none;}
+    text.terminal         {font-family: Verdana, Sans-serif;
+                            font-size: 12px;
+                            fill: #141000;
+                            font-weight: bold;
+                          }
+    text.nonterminal      {font-family: Verdana, Sans-serif;
+                            font-size: 12px;
+                            fill: #1A1400;
+                            font-weight: normal;
+                          }
+    text.regexp           {font-family: Verdana, Sans-serif;
+                            font-size: 12px;
+                            fill: #1F1800;
+                            font-weight: normal;
+                          }
+    rect, circle, polygon {fill: #332900; stroke: #332900;}
+    rect.terminal         {fill: #FFDB4D; stroke: #332900;}
+    rect.nonterminal      {fill: #FFEC9E; stroke: #332900;}
+    rect.text             {fill: none; stroke: none;}    
+    polygon.regexp        {fill: #FFF4C7; stroke: #332900;}
+  </style>
+         </defs>
+         <polygon points="9 33 1 29 1 37"/>
+         <polygon points="17 33 9 29 9 37"/>
+         <polygon points="51 35 58 19 152 19 159 35 152 51 58 51"/>
+         <polygon points="49 33 56 17 150 17 157 33 150 49 56 49" class="regexp"/>
+         <text class="regexp" x="64" y="37">[^{space},]</text>
+         <svg:path xmlns:svg="http://www.w3.org/2000/svg" class="line" d="m17 33 h2 m20 0 h10 m108 0 h10 m-148 0 l20 0 m-1 0 q-9 0 -9 -10 l0 -12 q0 -10 10 -10 m128 32 l20 0 m-20 0 q10 0 10 -10 l0 -12 q0 -10 -10 -10 m-128 0 h10 m0 0 h118 m23 32 h-3"/>
+         <polygon points="197 33 205 29 205 37"/>
+         <polygon points="197 33 189 29 189 37"/></svg><xhtml:p xmlns:xhtml="http://www.w3.org/1999/xhtml">
+         <xhtml:div class="ebnf"><xhtml:code>
+               <div><a href="#UnquotedString" title="UnquotedString">UnquotedString</a></div>
+               <div>         ::= [^{space},]+</div></xhtml:code></xhtml:div>
+      </xhtml:p>
+      <xhtml:p xmlns:xhtml="http://www.w3.org/1999/xhtml">referenced by:
+         <xhtml:ul>
+            <xhtml:li><xhtml:a href="#StringLiteral" title="StringLiteral">StringLiteral</xhtml:a></xhtml:li>
+         </xhtml:ul>
+      </xhtml:p><xhtml:br xmlns:xhtml="http://www.w3.org/1999/xhtml" /><xhtml:p xmlns:xhtml="http://www.w3.org/1999/xhtml" style="font-size: 14px; font-weight:bold"><xhtml:a name="NumberLiteral">NumberLiteral:</xhtml:a></xhtml:p><svg xmlns="http://www.w3.org/2000/svg" width="377" height="305">
+         <defs>
+            <style type="text/css">
+    @namespace "http://www.w3.org/2000/svg";
+    .line                 {fill: none; stroke: #332900;}
+    .bold-line            {stroke: #141000; shape-rendering: crispEdges; stroke-width: 2; }
+    .thin-line            {stroke: #1F1800; shape-rendering: crispEdges}
+    .filled               {fill: #332900; stroke: none;}
+    text.terminal         {font-family: Verdana, Sans-serif;
+                            font-size: 12px;
+                            fill: #141000;
+                            font-weight: bold;
+                          }
+    text.nonterminal      {font-family: Verdana, Sans-serif;
+                            font-size: 12px;
+                            fill: #1A1400;
+                            font-weight: normal;
+                          }
+    text.regexp           {font-family: Verdana, Sans-serif;
+                            font-size: 12px;
+                            fill: #1F1800;
+                            font-weight: normal;
+                          }
+    rect, circle, polygon {fill: #332900; stroke: #332900;}
+    rect.terminal         {fill: #FFDB4D; stroke: #332900;}
+    rect.nonterminal      {fill: #FFEC9E; stroke: #332900;}
+    rect.text             {fill: none; stroke: none;}    
+    polygon.regexp        {fill: #FFF4C7; stroke: #332900;}
+  </style>
+         </defs>
+         <polygon points="9 51 1 47 1 55"/>
+         <polygon points="17 51 9 47 9 55"/>
+         <rect x="51" y="37" width="28" height="32" rx="10"/>
+         <rect x="49" y="35" width="28" height="32" class="terminal" rx="10"/>
+         <text class="terminal" x="59" y="55">0</text>
+         <polygon points="139 19 146 3 194 3 201 19 194 35 146 35"/>
+         <polygon points="137 17 144 1 192 1 199 17 192 33 144 33" class="regexp"/>
+         <text class="regexp" x="152" y="21">[0-7]</text>
+         <rect x="119" y="85" width="28" height="32" rx="10"/>
+         <rect x="117" y="83" width="28" height="32" class="terminal" rx="10"/>
+         <text class="terminal" x="127" y="103">x</text>
+         <polygon points="207 101 214 85 262 85 269 101 262 117 214 117"/>
+         <polygon points="205 99 212 83 260 83 267 99 260 115 212 115" class="regexp"/>
+         <text class="regexp" x="220" y="103">[0-9]</text>
+         <polygon points="207 145 214 129 260 129 267 145 260 161 214 161"/>
+         <polygon points="205 143 212 127 258 127 265 143 258 159 212 159" class="regexp"/>
+         <text class="regexp" x="220" y="147">[A-F]</text>
+         <polygon points="207 189 214 173 258 173 265 189 258 205 214 205"/>
+         <polygon points="205 187 212 171 256 171 263 187 256 203 212 203" class="regexp"/>
+         <text class="regexp" x="220" y="191">[a-f]</text>
+         <rect x="71" y="271" width="26" height="32" rx="10"/>
+         <rect x="69" y="269" width="26" height="32" class="terminal" rx="10"/>
+         <text class="terminal" x="79" y="289">-</text>
+         <polygon points="137 255 144 239 192 239 199 255 192 271 144 271"/>
+         <polygon points="135 253 142 237 190 237 197 253 190 269 142 269" class="regexp"/>
+         <text class="regexp" x="150" y="257">[1-9]</text>
+         <polygon points="239 255 246 239 294 239 301 255 294 271 246 271"/>
+         <polygon points="237 253 244 237 292 237 299 253 292 269 244 269" class="regexp"/>
+         <text class="regexp" x="252" y="257">[0-9]</text>
+         <svg:path xmlns:svg="http://www.w3.org/2000/svg" class="line" d="m17 51 h2 m20 0 h10 m28 0 h10 m40 0 h10 m0 0 h72 m-102 0 l20 0 m-1 0 q-9 0 -9 -10 l0 -14 q0 -10 10 -10 m82 34 l20 0 m-20 0 q10 0 10 -10 l0 -14 q0 -10 -10 -10 m-82 0 h10 m62 0 h10 m20 34 h88 m-230 0 h20 m210 0 h20 m-250 0 q10 0 10 10 m230 0 q0 -10 10 -10 m-240 10 v28 m230 0 v-28 m-230 28 q0 10 10 10 m210 0 q10 0 10 -10 m-220 10 h10 m28 0 h10 m40 0 h10 m62 0 h10 m-102 0 h20 m82 0 h20 m-122 0 q10 0 10 10 m102 0 q0 -10 10 -10 m-112 10 v24 m102 0 v-24 m-102 24 q0 10 10 10 m82 0 q10 0 10 -10 m-92 10 h10 m60 0 h10 m0 0 h2 m-92 -10 v20 m102 0 v-20 m-102 20 v24 m102 0 v-24 m-102 24 q0 10 10 10 m82 0 q10 0 10 -10 m-92 10 h10 m58 0 h10 m0 0 h4 m-122 -88 l20 0 m-1 0 q-9 0 -9 -10 l0 -12 q0 -10 10 -10 m122 32 l20 0 m-20 0 q10 0 10 -10 l0 -12 q0 -10 -10 -10 m-122 0 h10 m0 0 h112 m-278 -16 h20 m298 0 h20 m-338 0 q10 0 10 10 m318 0 q0 -10 10 -10 m-328 10 v182 m318 0 v-182 m-318 182 q0 10 10 10 m298 0 q10 0 10 -10 m-288 10 h10 m0 0 h36 m-66 0 h20 m46 0 h20 m-86 0 q10 0 10 10 m66 0 q0 -10 10 -10 m-76 10 v12 m66 0 v-12 m-66 12 q0 10 10 10 m46 0 q10 0 10 -10 m-56 10 h10 m26 0 h10 m20 -32 h10 m62 0 h10 m20 0 h10 m62 0 h10 m-102 0 l20 0 m-1 0 q-9 0 -9 -10 l0 -12 q0 -10 10 -10 m82 32 l20 0 m-20 0 q10 0 10 -10 l0 -12 q0 -10 -10 -10 m-82 0 h10 m0 0 h72 m20 32 h8 m23 -202 h-3"/>
+         <polygon points="367 51 375 47 375 55"/>
+         <polygon points="367 51 359 47 359 55"/></svg><xhtml:p xmlns:xhtml="http://www.w3.org/1999/xhtml">
+         <xhtml:div class="ebnf"><xhtml:code>
+               <div><a href="#NumberLiteral" title="NumberLiteral">NumberLiteral</a></div>
+               <div>         ::= '0' ( [0-7]* | 'x' [0-9A-Fa-f]+ )</div>
+               <div>           | '-'? [1-9] [0-9]+</div></xhtml:code></xhtml:div>
+      </xhtml:p>
+      <xhtml:p xmlns:xhtml="http://www.w3.org/1999/xhtml">referenced by:
+         <xhtml:ul>
+            <xhtml:li><xhtml:a href="#Value" title="Value">Value</xhtml:a></xhtml:li>
+         </xhtml:ul>
+      </xhtml:p><xhtml:br xmlns:xhtml="http://www.w3.org/1999/xhtml" /><xhtml:p xmlns:xhtml="http://www.w3.org/1999/xhtml" style="font-size: 14px; font-weight:bold"><xhtml:a name="PropertyName">PropertyName:</xhtml:a></xhtml:p><svg xmlns="http://www.w3.org/2000/svg" width="283" height="203">
+         <defs>
+            <style type="text/css">
+    @namespace "http://www.w3.org/2000/svg";
+    .line                 {fill: none; stroke: #332900;}
+    .bold-line            {stroke: #141000; shape-rendering: crispEdges; stroke-width: 2; }
+    .thin-line            {stroke: #1F1800; shape-rendering: crispEdges}
+    .filled               {fill: #332900; stroke: none;}
+    text.terminal         {font-family: Verdana, Sans-serif;
+                            font-size: 12px;
+                            fill: #141000;
+                            font-weight: bold;
+                          }
+    text.nonterminal      {font-family: Verdana, Sans-serif;
+                            font-size: 12px;
+                            fill: #1A1400;
+                            font-weight: normal;
+                          }
+    text.regexp           {font-family: Verdana, Sans-serif;
+                            font-size: 12px;
+                            fill: #1F1800;
+                            font-weight: normal;
+                          }
+    rect, circle, polygon {fill: #332900; stroke: #332900;}
+    rect.terminal         {fill: #FFDB4D; stroke: #332900;}
+    rect.nonterminal      {fill: #FFEC9E; stroke: #332900;}
+    rect.text             {fill: none; stroke: none;}    
+    polygon.regexp        {fill: #FFF4C7; stroke: #332900;}
+  </style>
+         </defs>
+         <polygon points="9 183 1 179 1 187"/>
+         <polygon points="17 183 9 179 9 187"/>
+         <polygon points="51 185 58 169 106 169 113 185 106 201 58 201"/>
+         <polygon points="49 183 56 167 104 167 111 183 104 199 56 199" class="regexp"/>
+         <text class="regexp" x="64" y="187">[A-Z]</text>
+         <polygon points="153 151 160 135 208 135 215 151 208 167 160 167"/>
+         <polygon points="151 149 158 133 206 133 213 149 206 165 158 165" class="regexp"/>
+         <text class="regexp" x="166" y="153">[A-Z]</text>
+         <polygon points="153 107 160 91 208 91 215 107 208 123 160 123"/>
+         <polygon points="151 105 158 89 206 89 213 105 206 121 158 121" class="regexp"/>
+         <text class="regexp" x="166" y="109">[0-9]</text>
+         <rect x="153" y="47" width="28" height="32" rx="10"/>
+         <rect x="151" y="45" width="28" height="32" class="terminal" rx="10"/>
+         <text class="terminal" x="161" y="65">_</text>
+         <rect x="51" y="3" width="24" height="32" rx="10"/>
+         <rect x="49" y="1" width="24" height="32" class="terminal" rx="10"/>
+         <text class="terminal" x="59" y="21">.</text>
+         <svg:path xmlns:svg="http://www.w3.org/2000/svg" class="line" d="m17 183 h2 m20 0 h10 m62 0 h10 m20 0 h10 m0 0 h72 m-102 0 l20 0 m-1 0 q-9 0 -9 -10 l0 -14 q0 -10 10 -10 m82 34 l20 0 m-20 0 q10 0 10 -10 l0 -14 q0 -10 -10 -10 m-82 0 h10 m62 0 h10 m-92 10 l0 -44 q0 -10 10 -10 m92 54 l0 -44 q0 -10 -10 -10 m-82 0 h10 m62 0 h10 m-92 10 l0 -44 q0 -10 10 -10 m92 54 l0 -44 q0 -10 -10 -10 m-82 0 h10 m28 0 h10 m0 0 h34 m-204 122 l20 0 m-1 0 q-9 0 -9 -10 l0 -146 q0 -10 10 -10 m204 166 l20 0 m-20 0 q10 0 10 -10 l0 -146 q0 -10 -10 -10 m-204 0 h10 m24 0 h10 m0 0 h160 m23 166 h-3"/>
+         <polygon points="273 183 281 179 281 187"/>
+         <polygon points="273 183 265 179 265 187"/></svg><xhtml:p xmlns:xhtml="http://www.w3.org/1999/xhtml">
+         <xhtml:div class="ebnf"><xhtml:code>
+               <div><a href="#PropertyName" title="PropertyName">PropertyName</a></div>
+               <div>         ::= [A-Z] [A-Z0-9_]* ( '.' [A-Z] [A-Z0-9_]* )*</div></xhtml:code></xhtml:div>
+      </xhtml:p>
+      <xhtml:p xmlns:xhtml="http://www.w3.org/1999/xhtml">referenced by:
+         <xhtml:ul>
+            <xhtml:li><xhtml:a href="#Definition" title="Definition">Definition</xhtml:a></xhtml:li>
+            <xhtml:li><xhtml:a href="#Query" title="Query">Query</xhtml:a></xhtml:li>
+         </xhtml:ul>
+      </xhtml:p><xhtml:br xmlns:xhtml="http://www.w3.org/1999/xhtml" /><xhtml:hr xmlns:xhtml="http://www.w3.org/1999/xhtml" />
+      <xhtml:p xmlns:xhtml="http://www.w3.org/1999/xhtml">
+         <xhtml:table class="signature" border="0">
+            <xhtml:tr>
+               <xhtml:td style="width: 100%"> </xhtml:td>
+               <xhtml:td valign="top">
+                  <xhtml:nobr class="signature">... generated by <xhtml:a name="Railroad-Diagram-Generator" class="signature" title="https://www.bottlecaps.de/rr/ui" href="https://www.bottlecaps.de/rr/ui" target="_blank">Railroad Diagram Generator</xhtml:a></xhtml:nobr>
+               </xhtml:td>
+               <xhtml:td><xhtml:a name="Railroad-Diagram-Generator" title="https://www.bottlecaps.de/rr/ui" href="https://www.bottlecaps.de/rr/ui" target="_blank"><svg xmlns="http://www.w3.org/2000/svg" width="16" height="16">
+                        <g transform="scale(0.178)">
+                           <circle cx="45" cy="45" r="45" style="stroke:none; fill:#FFCC00"/>
+                           <circle cx="45" cy="45" r="42" style="stroke:#332900; stroke-width:2px; fill:#FFCC00"/>
+                           <line x1="15" y1="15" x2="75" y2="75" stroke="#332900" style="stroke-width:9px;"/>
+                           <line x1="15" y1="75" x2="75" y2="15" stroke="#332900" style="stroke-width:9px;"/>
+                           <text x="7" y="54" style="font-size:26px; font-family:Arial, Sans-serif; font-weight:bold; fill: #332900">R</text>
+                           <text x="64" y="54" style="font-size:26px; font-family:Arial, Sans-serif; font-weight:bold; fill: #332900">R</text>
+                        </g></svg></xhtml:a></xhtml:td>
+            </xhtml:tr>
+         </xhtml:table>
+      </xhtml:p>
+   </body>
+</html>
\ No newline at end of file
diff --git a/crypto/property/property.c b/crypto/property/property.c
new file mode 100644 (file)
index 0000000..1f914cf
--- /dev/null
@@ -0,0 +1,508 @@
+/*
+ * Copyright 2019 The OpenSSL Project Authors. All Rights Reserved.
+ * Copyright (c) 2019, Oracle and/or its affiliates.  All rights reserved.
+ *
+ * Licensed under the Apache License 2.0 (the "License").  You may not use
+ * this file except in compliance with the License.  You can obtain a copy
+ * in the file LICENSE in the source distribution or at
+ * https://www.openssl.org/source/license.html
+ */
+
+#include <string.h>
+#include <stdio.h>
+#include <stdarg.h>
+#include <openssl/crypto.h>
+#include "internal/property.h"
+#include "internal/ctype.h"
+#include <openssl/lhash.h>
+#include <openssl/rand.h>
+#include "internal/thread_once.h"
+#include "internal/lhash.h"
+#include "internal/sparse_array.h"
+#include "property_lcl.h"
+
+/* The number of elements in the query cache before we initiate a flush */
+#define IMPL_CACHE_FLUSH_THRESHOLD  500
+
+typedef struct {
+    OSSL_PROPERTY_LIST *properties;
+    void *implementation;
+    void (*implementation_destruct)(void *);
+} IMPLEMENTATION;
+
+DEFINE_STACK_OF(IMPLEMENTATION)
+
+typedef struct {
+    const char *query;
+    void *result;
+    char body[1];
+} QUERY;
+
+DEFINE_LHASH_OF(QUERY);
+
+typedef struct {
+    int nid;
+    STACK_OF(IMPLEMENTATION) *impls;
+    LHASH_OF(QUERY) *cache;
+} ALGORITHM;
+
+struct ossl_method_store_st {
+    size_t nelem;
+    SPARSE_ARRAY_OF(ALGORITHM) *algs;
+    OSSL_PROPERTY_LIST *global_properties;
+    int need_flush;
+    unsigned int nbits;
+    unsigned char rand_bits[(IMPL_CACHE_FLUSH_THRESHOLD + 7) / 8];
+    CRYPTO_RWLOCK *lock;
+};
+
+typedef struct {
+    OSSL_METHOD_STORE *store;
+    LHASH_OF(QUERY) *cache;
+    size_t nelem;
+} IMPL_CACHE_FLUSH;
+
+DEFINE_SPARSE_ARRAY_OF(ALGORITHM);
+
+static void ossl_method_cache_flush(OSSL_METHOD_STORE *store, int nid);
+static void ossl_method_cache_flush_all(OSSL_METHOD_STORE *c);
+
+int ossl_property_read_lock(OSSL_METHOD_STORE *p)
+{
+    return p != NULL ? CRYPTO_THREAD_read_lock(p->lock) : 0;
+}
+
+int ossl_property_write_lock(OSSL_METHOD_STORE *p)
+{
+    return p != NULL ? CRYPTO_THREAD_write_lock(p->lock) : 0;
+}
+
+int ossl_property_unlock(OSSL_METHOD_STORE *p)
+{
+    return p != 0 ? CRYPTO_THREAD_unlock(p->lock) : 0;
+}
+
+int ossl_method_store_init(void)
+{
+    if (ossl_property_string_init()
+            && ossl_prop_defn_init()
+            && ossl_property_parse_init())
+        return 1;
+
+    ossl_method_store_cleanup();
+    return 0;
+}
+
+void ossl_method_store_cleanup(void)
+{
+    ossl_property_string_cleanup();
+    ossl_prop_defn_cleanup();
+}
+
+static CRYPTO_ONCE method_store_init_flag = CRYPTO_ONCE_STATIC_INIT;
+DEFINE_RUN_ONCE_STATIC(do_method_store_init)
+{
+    return OPENSSL_init_crypto(0, NULL)
+        && ossl_method_store_init()
+        && OPENSSL_atexit(&ossl_method_store_cleanup);
+}
+
+static unsigned long query_hash(const QUERY *a)
+{
+    return OPENSSL_LH_strhash(a->query);
+}
+
+static int query_cmp(const QUERY *a, const QUERY *b)
+{
+    return strcmp(a->query, b->query);
+}
+
+static void impl_free(IMPLEMENTATION *impl)
+{
+    if (impl != NULL) {
+        if (impl->implementation_destruct)
+            impl->implementation_destruct(impl->implementation);
+        OPENSSL_free(impl);
+    }
+}
+
+static void impl_cache_free(QUERY *elem)
+{
+    OPENSSL_free(elem);
+}
+
+static void alg_cleanup(size_t idx, ALGORITHM *a)
+{
+    if (a != NULL) {
+        sk_IMPLEMENTATION_pop_free(a->impls, &impl_free);
+        lh_QUERY_doall(a->cache, &impl_cache_free);
+        lh_QUERY_free(a->cache);
+        OPENSSL_free(a);
+    }
+}
+
+OSSL_METHOD_STORE *ossl_method_store_new(void)
+{
+    OSSL_METHOD_STORE *res = OPENSSL_zalloc(sizeof(*res));
+
+    if (!RUN_ONCE(&method_store_init_flag, do_method_store_init))
+        return 0;
+
+    if (res != NULL) {
+        if ((res->algs = ossl_sa_ALGORITHM_new()) == NULL) {
+            OPENSSL_free(res);
+            return NULL;
+        }
+        if ((res->lock = CRYPTO_THREAD_lock_new()) == NULL) {
+            OPENSSL_free(res->algs);
+            OPENSSL_free(res);
+            return NULL;
+        }
+    }
+    return res;
+}
+
+void ossl_method_store_free(OSSL_METHOD_STORE *store)
+{
+    if (store != NULL) {
+        ossl_sa_ALGORITHM_doall(store->algs, &alg_cleanup);
+        ossl_sa_ALGORITHM_free(store->algs);
+        ossl_property_free(store->global_properties);
+        CRYPTO_THREAD_lock_free(store->lock);
+        OPENSSL_free(store);
+    }
+}
+
+static ALGORITHM *ossl_method_store_retrieve(OSSL_METHOD_STORE *store, int nid)
+{
+    return ossl_sa_ALGORITHM_get(store->algs, nid);
+}
+
+static int ossl_method_store_insert(OSSL_METHOD_STORE *store, ALGORITHM *alg)
+{
+        return ossl_sa_ALGORITHM_set(store->algs, alg->nid, alg);
+}
+
+int ossl_method_store_add(OSSL_METHOD_STORE *store,
+                          int nid, const char *properties,
+                          void *implementation,
+                          void (*implementation_destruct)(void *))
+{
+    ALGORITHM *alg = NULL;
+    IMPLEMENTATION *impl;
+    int ret = 0;
+
+    if (nid <= 0 || implementation == NULL || store == NULL)
+        return 0;
+    if (properties == NULL)
+        properties = "";
+
+    /* Create new entry */
+    impl = OPENSSL_malloc(sizeof(*impl));
+    if (impl == NULL)
+        return 0;
+    impl->implementation = implementation;
+    impl->implementation_destruct = implementation_destruct;
+
+    /*
+     * Insert into the hash table if required.
+     *
+     * A write lock is used unconditionally because we wend our way down to the
+     * property string code which isn't locking friendly.
+     */
+    ossl_property_write_lock(store);
+    ossl_method_cache_flush(store, nid);
+    if ((impl->properties = ossl_prop_defn_get(properties)) == NULL) {
+        if ((impl->properties = ossl_parse_property(properties)) == NULL)
+            goto err;
+        ossl_prop_defn_set(properties, impl->properties);
+    }
+
+    alg = ossl_method_store_retrieve(store, nid);
+    if (alg == NULL) {
+        if ((alg = OPENSSL_zalloc(sizeof(*alg))) == NULL
+                || (alg->impls = sk_IMPLEMENTATION_new_null()) == NULL
+                || (alg->cache = lh_QUERY_new(&query_hash, &query_cmp)) == NULL)
+            goto err;
+        alg->nid = nid;
+        if (!ossl_method_store_insert(store, alg))
+            goto err;
+    }
+
+    /* Push onto stack */
+    if (sk_IMPLEMENTATION_push(alg->impls, impl))
+        ret = 1;
+    ossl_property_unlock(store);
+    if (ret == 0)
+        impl_free(impl);
+    return ret;
+
+err:
+    ossl_property_unlock(store);
+    alg_cleanup(0, alg);
+    impl_free(impl);
+    return 0;
+}
+
+int ossl_method_store_remove(OSSL_METHOD_STORE *store, int nid,
+                             const void *implementation)
+{
+    ALGORITHM *alg = NULL;
+    int i;
+
+    if (nid <= 0 || implementation == NULL || store == NULL)
+        return 0;
+
+    ossl_property_write_lock(store);
+    ossl_method_cache_flush(store, nid);
+    alg = ossl_method_store_retrieve(store, nid);
+    if (alg == NULL) {
+        ossl_property_unlock(store);
+        return 0;
+    }
+
+    /*
+     * A sorting find then a delete could be faster but these stacks should be
+     * relatively small, so we avoid the overhead.  Sorting could also surprise
+     * users when result orderings change (even though they are not guaranteed).
+     */
+    for (i = 0; i < sk_IMPLEMENTATION_num(alg->impls); i++) {
+        IMPLEMENTATION *impl = sk_IMPLEMENTATION_value(alg->impls, i);
+
+        if (impl->implementation == implementation) {
+            sk_IMPLEMENTATION_delete(alg->impls, i);
+            ossl_property_unlock(store);
+            impl_free(impl);
+            return 1;
+        }
+    }
+    ossl_property_unlock(store);
+    return 0;
+}
+
+int ossl_method_store_fetch(OSSL_METHOD_STORE *store, int nid,
+                            const char *prop_query, void **result)
+{
+    ALGORITHM *alg;
+    IMPLEMENTATION *impl;
+    OSSL_PROPERTY_LIST *pq = NULL, *p2;
+    int ret = 0;
+    int j;
+
+    if (nid <= 0 || result == NULL || store == NULL)
+        return 0;
+
+    /*
+     * This only needs to be a read lock, because queries never create property
+     * names or value and thus don't modify any of the property string layer.
+     */
+    ossl_property_read_lock(store);
+    alg = ossl_method_store_retrieve(store, nid);
+    if (alg == NULL) {
+        ossl_property_unlock(store);
+        return 0;
+    }
+
+    if (prop_query == NULL) {
+        if ((impl = sk_IMPLEMENTATION_value(alg->impls, 0)) != NULL) {
+            *result = impl->implementation;
+            ret = 1;
+        }
+        goto fin;
+    }
+    pq = ossl_parse_query(prop_query);
+    if (pq == NULL)
+        goto fin;
+    if (store->global_properties != NULL) {
+        p2 = ossl_property_merge(pq, store->global_properties);
+        if (p2 == NULL)
+            goto fin;
+        ossl_property_free(pq);
+        pq = p2;
+    }
+    for (j = 0; j < sk_IMPLEMENTATION_num(alg->impls); j++) {
+        impl = sk_IMPLEMENTATION_value(alg->impls, j);
+
+        if (ossl_property_match(pq, impl->properties)) {
+            *result = impl->implementation;
+            ret = 1;
+            goto fin;
+        }
+    }
+fin:
+    ossl_property_unlock(store);
+    ossl_property_free(pq);
+    return ret;
+}
+
+int ossl_method_store_set_global_properties(OSSL_METHOD_STORE *store,
+                                            const char *prop_query) {
+    int ret = 0;
+
+    if (store == NULL)
+        return 1;
+
+    ossl_property_write_lock(store);
+    ossl_method_cache_flush_all(store);
+    if (prop_query == NULL) {
+        ossl_property_free(store->global_properties);
+        store->global_properties = NULL;
+        ossl_property_unlock(store);
+        return 1;
+    }
+    store->global_properties = ossl_parse_query(prop_query);
+    ret = store->global_properties != NULL;
+    ossl_property_unlock(store);
+    return ret;
+}
+
+static void impl_cache_flush_alg(size_t idx, ALGORITHM *alg)
+{
+    lh_QUERY_doall(alg->cache, &impl_cache_free);
+    lh_QUERY_flush(alg->cache);
+}
+
+static void ossl_method_cache_flush(OSSL_METHOD_STORE *store, int nid)
+{
+    ALGORITHM *alg = ossl_method_store_retrieve(store, nid);
+
+    if (alg != NULL) {
+        store->nelem -= lh_QUERY_num_items(alg->cache);
+        impl_cache_flush_alg(0, alg);
+    }
+}
+
+static void ossl_method_cache_flush_all(OSSL_METHOD_STORE *store)
+{
+    ossl_sa_ALGORITHM_doall(store->algs, &impl_cache_flush_alg);
+    store->nelem = 0;
+}
+
+IMPLEMENT_LHASH_DOALL_ARG(QUERY, IMPL_CACHE_FLUSH);
+
+/*
+ * Flush an element from the query cache (perhaps).
+ *
+ * In order to avoid taking a write lock to keep accurate LRU information or
+ * using atomic operations to approximate similar, the procedure used here
+ * is to stochastically flush approximately half the cache.  Since generating
+ * random numbers is relatively expensive, we produce them in blocks and
+ * consume them as we go, saving generated bits between generations of flushes.
+ *
+ * This procedure isn't ideal, LRU would be better.  However, in normal
+ * operation, reaching a full cache would be quite unexpected.  It means
+ * that no steady state of algorithm queries has been reached.  I.e. it is most
+ * likely an attack of some form.  A suboptimal clearance strategy that doesn't
+ * degrade performance of the normal case is preferable to a more refined
+ * approach that imposes a performance impact.
+ */
+static void impl_cache_flush_cache(QUERY *c, IMPL_CACHE_FLUSH *state)
+{
+    OSSL_METHOD_STORE *store = state->store;
+    unsigned int n;
+
+    if (store->nbits == 0) {
+        if (!RAND_bytes(store->rand_bits, sizeof(store->rand_bits)))
+            return;
+        store->nbits = sizeof(store->rand_bits) * 8;
+    }
+    n = --store->nbits;
+    if ((store->rand_bits[n >> 3] & (1 << (n & 7))) != 0)
+        OPENSSL_free(lh_QUERY_delete(state->cache, c));
+    else
+        state->nelem++;
+}
+
+static void impl_cache_flush_one_alg(size_t idx, ALGORITHM *alg, void *v)
+{
+    IMPL_CACHE_FLUSH *state = (IMPL_CACHE_FLUSH *)v;
+
+    state->cache = alg->cache;
+    lh_QUERY_doall_IMPL_CACHE_FLUSH(state->cache, &impl_cache_flush_cache,
+                                    state);
+}
+
+static void ossl_method_cache_flush_some(OSSL_METHOD_STORE *store)
+{
+    IMPL_CACHE_FLUSH state;
+
+    state.nelem = 0;
+    state.store = store;
+    ossl_sa_ALGORITHM_doall_arg(store->algs, &impl_cache_flush_one_alg, &state);
+    store->need_flush = 0;
+    store->nelem = state.nelem;
+}
+
+int ossl_method_store_cache_get(OSSL_METHOD_STORE *store, int nid,
+                                const char *prop_query, void **result)
+{
+    ALGORITHM *alg;
+    QUERY elem, *r;
+
+    if (nid <= 0 || store == NULL)
+        return 0;
+
+    ossl_property_read_lock(store);
+    alg = ossl_method_store_retrieve(store, nid);
+    if (alg == NULL) {
+        ossl_property_unlock(store);
+        return 0;
+    }
+
+    elem.query = prop_query;
+    r = lh_QUERY_retrieve(alg->cache, &elem);
+    if (r == NULL) {
+        ossl_property_unlock(store);
+        return 0;
+    }
+    *result = r->result;
+    ossl_property_unlock(store);
+    return 1;
+}
+
+int ossl_method_store_cache_set(OSSL_METHOD_STORE *store, int nid,
+                                const char *prop_query, void *result)
+{
+    QUERY elem, *old, *p = NULL;
+    ALGORITHM *alg;
+    size_t len;
+
+    if (nid <= 0 || store == NULL)
+        return 0;
+    if (prop_query == NULL)
+        return 1;
+
+    ossl_property_write_lock(store);
+    if (store->need_flush)
+        ossl_method_cache_flush_some(store);
+    alg = ossl_method_store_retrieve(store, nid);
+    if (alg == NULL) {
+        ossl_property_unlock(store);
+        return 0;
+    }
+
+    if (result == NULL) {
+        elem.query = prop_query;
+        lh_QUERY_delete(alg->cache, &elem);
+        ossl_property_unlock(store);
+        return 1;
+    }
+    p = OPENSSL_malloc(sizeof(*p) + (len = strlen(prop_query)));
+    if (p != NULL) {
+        p->query = p->body;
+        p->result = result;
+        memcpy((char *)p->query, prop_query, len + 1);
+        if ((old = lh_QUERY_insert(alg->cache, p)) != NULL)
+            OPENSSL_free(old);
+        if (old != NULL || !lh_QUERY_error(alg->cache)) {
+            store->nelem++;
+            if (store->nelem >= IMPL_CACHE_FLUSH_THRESHOLD)
+                store->need_flush = 1;
+            ossl_property_unlock(store);
+            return 1;
+        }
+    }
+    ossl_property_unlock(store);
+    OPENSSL_free(p);
+    return 0;
+}
diff --git a/crypto/property/property_lcl.h b/crypto/property/property_lcl.h
new file mode 100644 (file)
index 0000000..faf3fe1
--- /dev/null
@@ -0,0 +1,51 @@
+/*
+ * Copyright 2019 The OpenSSL Project Authors. All Rights Reserved.
+ * Copyright (c) 2019, Oracle and/or its affiliates.  All rights reserved.
+ *
+ * Licensed under the Apache License 2.0 (the "License").  You may not use
+ * this file except in compliance with the License.  You can obtain a copy
+ * in the file LICENSE in the source distribution or at
+ * https://www.openssl.org/source/license.html
+ */
+
+#include <openssl/crypto.h>
+#include "internal/property.h"
+
+typedef struct ossl_property_list_st OSSL_PROPERTY_LIST;
+typedef int OSSL_PROPERTY_IDX;
+
+/* Initialisation and finalisation for subsystem */
+int ossl_method_store_init(void);
+void ossl_method_store_cleanup(void);
+
+/* Property string functions */
+OSSL_PROPERTY_IDX ossl_property_name(const char *s, int create);
+OSSL_PROPERTY_IDX ossl_property_value(const char *s, int create);
+int ossl_property_string_init(void);
+void ossl_property_string_cleanup(void);
+
+/* Property list functions */
+int ossl_property_parse_init(void);
+void ossl_property_free(OSSL_PROPERTY_LIST *p);
+int ossl_property_match(const OSSL_PROPERTY_LIST *query,
+                        const OSSL_PROPERTY_LIST *defn);
+OSSL_PROPERTY_LIST *ossl_property_merge(const OSSL_PROPERTY_LIST *a,
+                                        const OSSL_PROPERTY_LIST *b);
+
+/* Property definition functions */
+OSSL_PROPERTY_LIST *ossl_parse_property(const char *s);
+
+/* Property query functions */
+OSSL_PROPERTY_LIST *ossl_parse_query(const char *s);
+
+/* Property definition cache functions */
+int ossl_prop_defn_init(void);
+void ossl_prop_defn_cleanup(void);
+OSSL_PROPERTY_LIST *ossl_prop_defn_get(const char *prop);
+int ossl_prop_defn_set(const char *prop, OSSL_PROPERTY_LIST *pl);
+
+/* Property cache lock / unlock */
+int ossl_property_write_lock(OSSL_METHOD_STORE *);
+int ossl_property_read_lock(OSSL_METHOD_STORE *);
+int ossl_property_unlock(OSSL_METHOD_STORE *);
+
diff --git a/crypto/property/property_parse.c b/crypto/property/property_parse.c
new file mode 100644 (file)
index 0000000..2094d38
--- /dev/null
@@ -0,0 +1,545 @@
+/*
+ * Copyright 2019 The OpenSSL Project Authors. All Rights Reserved.
+ * Copyright (c) 2019, Oracle and/or its affiliates.  All rights reserved.
+ *
+ * Licensed under the Apache License 2.0 (the "License").  You may not use
+ * this file except in compliance with the License.  You can obtain a copy
+ * in the file LICENSE in the source distribution or at
+ * https://www.openssl.org/source/license.html
+ */
+
+#include <string.h>
+#include <stdio.h>
+#include <stdarg.h>
+#include <openssl/err.h>
+#include "internal/propertyerr.h"
+#include "internal/property.h"
+#include "internal/ctype.h"
+#include "internal/nelem.h"
+#include "property_lcl.h"
+#include "e_os.h"
+
+typedef enum {
+    PROPERTY_TYPE_STRING, PROPERTY_TYPE_NUMBER,
+    PROPERTY_TYPE_VALUE_UNDEFINED
+} PROPERTY_TYPE;
+
+typedef enum {
+    PROPERTY_OPER_EQ, PROPERTY_OPER_NE, PROPERTY_OVERRIDE
+} PROPERTY_OPER;
+
+typedef struct {
+    OSSL_PROPERTY_IDX name_idx;
+    PROPERTY_TYPE type;
+    PROPERTY_OPER oper;
+    union {
+        int64_t             int_val;     /* Signed integer */
+        OSSL_PROPERTY_IDX   str_val;     /* String */
+    } v;
+} PROPERTY_DEFINITION;
+
+struct ossl_property_list_st {
+    int n;
+    PROPERTY_DEFINITION properties[1];
+};
+
+static OSSL_PROPERTY_IDX ossl_property_true, ossl_property_false;
+
+DEFINE_STACK_OF(PROPERTY_DEFINITION)
+
+static const char *skip_space(const char *s)
+{
+    while (ossl_isspace(*s))
+        s++;
+    return s;
+}
+
+static int match_ch(const char *t[], char m)
+{
+    const char *s = *t;
+
+    if (*s == m) {
+        *t = skip_space(s + 1);
+        return 1;
+    }
+    return 0;
+}
+
+#define MATCH(s, m) match(s, m, sizeof(m) - 1)
+
+static int match(const char *t[], const char m[], size_t m_len)
+{
+    const char *s = *t;
+
+    if (strncasecmp(s, m, m_len) == 0) {
+        *t = skip_space(s + m_len);
+        return 1;
+    }
+    return 0;
+}
+
+static int parse_name(const char *t[], int create, OSSL_PROPERTY_IDX *idx)
+{
+    char name[100];
+    int err = 0;
+    size_t i = 0;
+    const char *s = *t;
+    int user_name = 0;
+
+    for (;;) {
+        if (!ossl_isalpha(*s)) {
+            PROPerr(PROP_F_PARSE_NAME, PROP_R_NOT_AN_IDENTIFIER);
+            return 0;
+        }
+        do {
+            if (i < sizeof(name) - 1)
+                name[i++] = ossl_tolower(*s);
+            else
+                err = 1;
+        } while (*++s == '_' || ossl_isalnum(*s));
+        if (*s != '.')
+            break;
+        user_name = 1;
+        if (i < sizeof(name) - 1)
+            name[i++] = *s;
+        else
+            err = 1;
+        s++;
+    }
+    name[i] = '\0';
+    *t = skip_space(s);
+    if (!err) {
+        *idx = ossl_property_name(name, user_name && create);
+        return 1;
+    }
+    PROPerr(PROP_F_PARSE_NAME, PROP_R_NAME_TOO_LONG);
+    return 0;
+}
+
+static int parse_number(const char *t[], PROPERTY_DEFINITION *res)
+{
+    const char *s = *t;
+    int64_t v = 0;
+
+    if (!ossl_isdigit(*s))
+        return 0;
+    do {
+        v = v * 10 + (*s++ - '0');
+    } while (ossl_isdigit(*s));
+    if (!ossl_isspace(*s) && *s != '\0' && *s != ',') {
+        PROPerr(PROP_F_PARSE_NUMBER, PROP_R_NOT_A_DECIMAL_DIGIT);
+        return 0;
+    }
+    *t = skip_space(s);
+    res->type = PROPERTY_TYPE_NUMBER;
+    res->v.int_val = v;
+    return 1;
+}
+
+static int parse_hex(const char *t[], PROPERTY_DEFINITION *res)
+{
+    const char *s = *t;
+    int64_t v = 0;
+
+    if (!ossl_isxdigit(*s))
+        return 0;
+    do {
+        v <<= 4;
+        if (ossl_isdigit(*s))
+            v += *s - '0';
+        else
+            v += ossl_tolower(*s) - 'a';
+    } while (ossl_isxdigit(*++s));
+    if (!ossl_isspace(*s) && *s != '\0' && *s != ',') {
+        PROPerr(PROP_F_PARSE_HEX, PROP_R_NOT_AN_HEXADECIMAL_DIGIT);
+        return 0;
+    }
+    *t = skip_space(s);
+    res->type = PROPERTY_TYPE_NUMBER;
+    res->v.int_val = v;
+    return 1;
+}
+
+static int parse_oct(const char *t[], PROPERTY_DEFINITION *res)
+{
+    const char *s = *t;
+    int64_t v = 0;
+
+    if (*s == '9' || *s == '8' || !ossl_isdigit(*s))
+        return 0;
+    do {
+        v = (v << 3) + (*s - '0');
+    } while (ossl_isdigit(*++s) && *s != '9' && *s != '8');
+    if (!ossl_isspace(*s) && *s != '\0' && *s != ',') {
+        PROPerr(PROP_F_PARSE_OCT, PROP_R_NOT_AN_OCTAL_DIGIT);
+        return 0;
+    }
+    *t = skip_space(s);
+    res->type = PROPERTY_TYPE_NUMBER;
+    res->v.int_val = v;
+    return 1;
+}
+
+static int parse_string(const char *t[], char delim, PROPERTY_DEFINITION *res,
+                        const int create)
+{
+    char v[1000];
+    const char *s = *t;
+    size_t i = 0;
+    int err = 0;
+
+    while (*s != '\0' && *s != delim) {
+        if (i < sizeof(v) - 1)
+            v[i++] = *s;
+        else
+            err = 1;
+        s++;
+    }
+    if (*s == '\0') {
+        PROPerr(PROP_F_PARSE_STRING,
+                PROP_R_NO_MATCHING_STRING_DELIMETER);
+        return 0;
+    }
+    v[i] = '\0';
+    *t = skip_space(s + 1);
+    if (err)
+        PROPerr(PROP_F_PARSE_STRING, PROP_R_STRING_TOO_LONG);
+    else
+        res->v.str_val = ossl_property_value(v, create);
+    res->type = PROPERTY_TYPE_STRING;
+    return !err;
+}
+
+static int parse_unquoted(const char *t[], PROPERTY_DEFINITION *res,
+                          const int create)
+{
+    char v[1000];
+    const char *s = *t;
+    size_t i = 0;
+    int err = 0;
+
+    if (*s == '\0' || *s == ',')
+        return 0;
+    while (ossl_isprint(*s) && !ossl_isspace(*s) && *s != ',') {
+        if (i < sizeof(v) - 1)
+            v[i++] = ossl_tolower(*s);
+        else
+            err = 1;
+        s++;
+    }
+    if (!ossl_isspace(*s) && *s != '\0' && *s != ',') {
+        PROPerr(PROP_F_PARSE_UNQUOTED, PROP_R_NOT_AN_ASCII_CHARACTER);
+        return 0;
+    }
+    v[i] = 0;
+    *t = skip_space(s);
+    if (err)
+        PROPerr(PROP_F_PARSE_UNQUOTED, PROP_R_STRING_TOO_LONG);
+    else
+        res->v.str_val = ossl_property_value(v, create);
+    res->type = PROPERTY_TYPE_STRING;
+    return !err;
+}
+
+static int parse_value(const char *t[], PROPERTY_DEFINITION *res, int create)
+{
+    const char *s = *t;
+    int r = 0;
+
+    if (*s == '"' || *s == '\'') {
+        s++;
+        r = parse_string(&s, s[-1], res, create);
+    } else if (*s == '+') {
+        s++;
+        r = parse_number(&s, res);
+    } else if (*s == '-') {
+        s++;
+        r = parse_number(&s, res);
+        res->v.int_val = -res->v.int_val;
+    } else if (*s == '0' && s[1] == 'x') {
+        s += 2;
+        r = parse_hex(&s, res);
+    } else if (*s == '0' && ossl_isdigit(s[1])) {
+        s++;
+        r = parse_oct(&s, res);
+    } else if (ossl_isdigit(*s)) {
+        return parse_number(t, res);
+    } else if (ossl_isalpha(*s))
+        return parse_unquoted(t, res, create);
+    if (r)
+        *t = s;
+    return r;
+}
+
+static int pd_compare(const PROPERTY_DEFINITION *const *p1,
+                      const PROPERTY_DEFINITION *const *p2)
+{
+    const PROPERTY_DEFINITION *pd1 = *p1;
+    const PROPERTY_DEFINITION *pd2 = *p2;
+
+    if (pd1->name_idx < pd2->name_idx)
+        return -1;
+    if (pd1->name_idx > pd2->name_idx)
+        return 1;
+    return 0;
+}
+
+static void pd_free(PROPERTY_DEFINITION *pd)
+{
+    OPENSSL_free(pd);
+}
+
+/*
+ * Convert a stack of property definitions and queries into a fixed array.
+ * The items are sorted for efficient query.  The stack is not freed.
+ */
+static OSSL_PROPERTY_LIST *stack_to_property_list(STACK_OF(PROPERTY_DEFINITION)
+                                                  *sk)
+{
+    const int n = sk_PROPERTY_DEFINITION_num(sk);
+    OSSL_PROPERTY_LIST *r;
+    int i;
+
+    r = OPENSSL_malloc(sizeof(*r)
+                       + (n == 0 ? 0 : n - 1) * sizeof(r->properties[0]));
+    if (r != NULL) {
+        sk_PROPERTY_DEFINITION_sort(sk);
+
+        for (i = 0; i < n; i++)
+            r->properties[i] = *sk_PROPERTY_DEFINITION_value(sk, i);
+        r->n = n;
+    }
+    return r;
+}
+
+OSSL_PROPERTY_LIST *ossl_parse_property(const char *defn)
+{
+    PROPERTY_DEFINITION *prop = NULL;
+    OSSL_PROPERTY_LIST *res = NULL;
+    STACK_OF(PROPERTY_DEFINITION) *sk;
+    const char *s = defn;
+    int done;
+
+    if (s == NULL || (sk = sk_PROPERTY_DEFINITION_new(&pd_compare)) == NULL)
+        return NULL;
+
+    s = skip_space(s);
+    done = *s == '\0';
+    while (!done) {
+        prop = OPENSSL_malloc(sizeof(*prop));
+        if (prop == NULL)
+            goto err;
+        memset(&prop->v, 0, sizeof(prop->v));
+        if (!parse_name(&s, 1, &prop->name_idx))
+            goto err;
+        prop->oper = PROPERTY_OPER_EQ;
+        if (prop->name_idx == 0) {
+            PROPerr(PROP_F_OSSL_PARSE_PROPERTY, PROP_R_PARSE_FAILED);
+            goto err;
+        }
+        if (match_ch(&s, '=')) {
+            if (!parse_value(&s, prop, 1)) {
+                PROPerr(PROP_F_OSSL_PARSE_PROPERTY, PROP_R_NO_VALUE);
+                goto err;
+            }
+        } else {
+            /* A name alone means a true Boolean */
+            prop->type = PROPERTY_TYPE_STRING;
+            prop->v.str_val = ossl_property_true;
+        }
+
+        if (!sk_PROPERTY_DEFINITION_push(sk, prop))
+            goto err;
+        prop = NULL;
+        done = !match_ch(&s, ',');
+    }
+    if (*s != '\0') {
+        PROPerr(PROP_F_OSSL_PARSE_PROPERTY, PROP_R_TRAILING_CHARACTERS);
+        goto err;
+    }
+    res = stack_to_property_list(sk);
+
+err:
+    OPENSSL_free(prop);
+    sk_PROPERTY_DEFINITION_pop_free(sk, &pd_free);
+    return res;
+}
+
+OSSL_PROPERTY_LIST *ossl_parse_query(const char *s)
+{
+    STACK_OF(PROPERTY_DEFINITION) *sk;
+    OSSL_PROPERTY_LIST *res = NULL;
+    PROPERTY_DEFINITION *prop = NULL;
+    int done;
+
+    if (s == NULL || (sk = sk_PROPERTY_DEFINITION_new(&pd_compare)) == NULL)
+        return NULL;
+
+    s = skip_space(s);
+    done = *s == '\0';
+    while (!done) {
+        prop = OPENSSL_malloc(sizeof(*prop));
+        if (prop == NULL)
+            goto err;
+        memset(&prop->v, 0, sizeof(prop->v));
+
+        if (match_ch(&s, '-')) {
+            prop->oper = PROPERTY_OVERRIDE;
+            if (!parse_name(&s, 0, &prop->name_idx))
+                goto err;
+            goto skip_value;
+        }
+        if (!parse_name(&s, 0, &prop->name_idx))
+            goto err;
+
+        if (match_ch(&s, '=')) {
+            prop->oper = PROPERTY_OPER_EQ;
+        } else if (MATCH(&s, "!=")) {
+            prop->oper = PROPERTY_OPER_NE;
+        } else {
+            /* A name alone is a Boolean comparison for true */
+            prop->oper = PROPERTY_OPER_EQ;
+            prop->type = PROPERTY_TYPE_STRING;
+            prop->v.str_val = ossl_property_true;
+            goto skip_value;
+        }
+        if (!parse_value(&s, prop, 0))
+            prop->type = PROPERTY_TYPE_VALUE_UNDEFINED;
+
+skip_value:
+        if (!sk_PROPERTY_DEFINITION_push(sk, prop))
+            goto err;
+        prop = NULL;
+        done = !match_ch(&s, ',');
+    }
+    if (*s != '\0') {
+        PROPerr(PROP_F_OSSL_PARSE_QUERY, PROP_R_TRAILING_CHARACTERS);
+        goto err;
+    }
+    res = stack_to_property_list(sk);
+
+err:
+    OPENSSL_free(prop);
+    sk_PROPERTY_DEFINITION_pop_free(sk, &pd_free);
+    return res;
+}
+
+int ossl_property_match(const OSSL_PROPERTY_LIST *query,
+                        const OSSL_PROPERTY_LIST *defn)
+{
+    const PROPERTY_DEFINITION *const q = query->properties;
+    const PROPERTY_DEFINITION *const d = defn->properties;
+    int i = 0, j = 0;
+    PROPERTY_OPER oper;
+
+    while (i < query->n) {
+        if ((oper = q[i].oper) == PROPERTY_OVERRIDE) {
+            i++;
+            continue;
+        }
+        if (j < defn->n) {
+            if (q[i].name_idx > d[j].name_idx) {  /* skip defn, not in query */
+                j++;
+                continue;
+            }
+            if (q[i].name_idx == d[j].name_idx) { /* both in defn and query */
+                const int eq = q[i].type == d[j].type
+                               && memcmp(&q[i].v, &d[j].v, sizeof(q[i].v)) == 0;
+
+                if ((eq && oper != PROPERTY_OPER_EQ)
+                    || (!eq && oper != PROPERTY_OPER_NE))
+                    return 0;
+                i++;
+                j++;
+                continue;
+            }
+        }
+
+        /*
+         * Handle the cases of a missing value and a query with no corresponding
+         * definition.  The former fails for any comparision except inequality,
+         * the latter is treated as a comparison against the Boolean false.
+         */
+        if (q[i].type == PROPERTY_TYPE_VALUE_UNDEFINED) {
+            if (oper != PROPERTY_OPER_NE)
+                return 0;
+        } else if (q[i].type != PROPERTY_TYPE_STRING
+                   || (oper == PROPERTY_OPER_EQ
+                       && q[i].v.str_val != ossl_property_false)
+                   || (oper == PROPERTY_OPER_NE
+                       && q[i].v.str_val == ossl_property_false)) {
+            return 0;
+        }
+        i++;
+    }
+    return 1;
+}
+
+void ossl_property_free(OSSL_PROPERTY_LIST *p)
+{
+    OPENSSL_free(p);
+}
+
+/*
+ * Merge two property lists.
+ * If there is a common name, the one from the first list is used.
+ */
+OSSL_PROPERTY_LIST *ossl_property_merge(const OSSL_PROPERTY_LIST *a,
+                                        const OSSL_PROPERTY_LIST *b)
+{
+    const PROPERTY_DEFINITION *const ap = a->properties;
+    const PROPERTY_DEFINITION *const bp = b->properties;
+    const PROPERTY_DEFINITION *copy;
+    OSSL_PROPERTY_LIST *r;
+    int i, j, n;
+    const int t = a->n + b->n;
+
+    r = OPENSSL_malloc(sizeof(*r)
+                       + (t == 0 ? 0 : t - 1) * sizeof(r->properties[0]));
+    if (r == NULL)
+        return NULL;
+
+    for (i = j = n = 0; i < a->n || j < b->n; n++) {
+        if (i >= a->n) {
+            copy = &bp[j++];
+        } else if (j >= b->n) {
+            copy = &ap[i++];
+        } else if (ap[i].name_idx <= bp[j].name_idx) {
+            if (ap[i].name_idx == bp[j].name_idx)
+                j++;
+            copy = &ap[i++];
+        } else {
+            copy = &bp[j++];
+        }
+        memcpy(r->properties + n, copy, sizeof(r->properties[0]));
+    }
+    r->n = n;
+    if (n != t)
+        r = OPENSSL_realloc(r, sizeof(*r) + (n - 1) * sizeof(r->properties[0]));
+    return r;
+}
+
+int ossl_property_parse_init(void)
+{
+    static const char *const predefined_names[] = {
+        "default",      /* Being provided by the default built-in provider */
+        "provider",     /* Name of provider (default, fips) */
+        "version",      /* Version number of this provider */
+        "fips",         /* FIPS supporting provider */
+        "engine",       /* An old style engine masquerading as a provider */
+    };
+    size_t i;
+
+    for (i = 0; i < OSSL_NELEM(predefined_names); i++)
+        if (ossl_property_name(predefined_names[i], 1) == 0)
+            goto err;
+
+    /* Pre-populate the two Boolean values */
+    if ((ossl_property_true = ossl_property_value("yes", 1)) == 0
+        || (ossl_property_false = ossl_property_value("no", 1)) == 0)
+        goto err;
+
+    return 1;
+err:
+    return 0;
+}
diff --git a/crypto/property/property_string.c b/crypto/property/property_string.c
new file mode 100644 (file)
index 0000000..7f6e30e
--- /dev/null
@@ -0,0 +1,137 @@
+/*
+ * Copyright 2019 The OpenSSL Project Authors. All Rights Reserved.
+ * Copyright (c) 2019, Oracle and/or its affiliates.  All rights reserved.
+ *
+ * Licensed under the Apache License 2.0 (the "License").  You may not use
+ * this file except in compliance with the License.  You can obtain a copy
+ * in the file LICENSE in the source distribution or at
+ * https://www.openssl.org/source/license.html
+ */
+
+#include <string.h>
+#include <openssl/crypto.h>
+#include <openssl/lhash.h>
+#include "internal/lhash.h"
+#include "property_lcl.h"
+
+/*
+ * Property strings are a consolidation of all strings seen by the property
+ * subsystem.  There are two name spaces to keep property names separate from
+ * property values (numeric values are not expected to be cached however).
+ * They allow a rapid conversion from a string to a unique index and any
+ * subsequent string comparison can be done via an integer compare.
+ *
+ * This implementation uses OpenSSL's standard hash table.  There are more
+ * space and time efficient algorithms if this becomes a bottleneck.
+ */
+
+typedef struct {
+    const char *s;
+    OSSL_PROPERTY_IDX idx;
+    char body[1];
+} PROPERTY_STRING;
+
+DEFINE_LHASH_OF(PROPERTY_STRING);
+typedef LHASH_OF(PROPERTY_STRING) PROP_TABLE;
+
+static PROP_TABLE *prop_names;
+static PROP_TABLE *prop_values;
+static OSSL_PROPERTY_IDX prop_name_idx = 0;
+static OSSL_PROPERTY_IDX prop_value_idx = 0;
+
+static unsigned long property_hash(const PROPERTY_STRING *a)
+{
+    return OPENSSL_LH_strhash(a->s);
+}
+
+static int property_cmp(const PROPERTY_STRING *a, const PROPERTY_STRING *b)
+{
+    return strcmp(a->s, b->s);
+}
+
+static void property_free(PROPERTY_STRING *ps)
+{
+    OPENSSL_free(ps);
+}
+
+static void property_table_free(PROP_TABLE **pt)
+{
+    PROP_TABLE *t = *pt;
+
+    if (t != NULL) {
+        lh_PROPERTY_STRING_doall(t, &property_free);
+        lh_PROPERTY_STRING_free(t);
+        *pt = NULL;
+    }
+}
+
+static PROPERTY_STRING *new_property_string(const char *s,
+                                            OSSL_PROPERTY_IDX *pidx)
+{
+    const size_t l = strlen(s);
+    PROPERTY_STRING *ps = OPENSSL_malloc(sizeof(*ps) + l);
+
+    if (ps != NULL) {
+        memcpy(ps->body, s, l + 1);
+        ps->s = ps->body;
+        ps->idx = ++*pidx;
+        if (ps->idx == 0) {
+            OPENSSL_free(ps);
+            return NULL;
+        }
+    }
+    return ps;
+}
+
+static OSSL_PROPERTY_IDX ossl_property_string(PROP_TABLE *t,
+                                              OSSL_PROPERTY_IDX *pidx,
+                                              const char *s)
+{
+    PROPERTY_STRING p, *ps, *ps_new;
+
+    p.s = s;
+    ps = lh_PROPERTY_STRING_retrieve(t, &p);
+    if (ps == NULL && pidx != NULL)
+        if ((ps_new = new_property_string(s, pidx)) != NULL) {
+            lh_PROPERTY_STRING_insert(t, ps_new);
+            if (lh_PROPERTY_STRING_error(t)) {
+                property_free(ps_new);
+                return 0;
+            }
+            ps = ps_new;
+        }
+    return ps != NULL ? ps->idx : 0;
+}
+
+OSSL_PROPERTY_IDX ossl_property_name(const char *s, int create)
+{
+    return ossl_property_string(prop_names, create ? &prop_name_idx : NULL, s);
+}
+
+OSSL_PROPERTY_IDX ossl_property_value(const char *s, int create)
+{
+    return ossl_property_string(prop_values, create ? &prop_value_idx : NULL, s);
+}
+
+int ossl_property_string_init(void)
+{
+    prop_names = lh_PROPERTY_STRING_new(&property_hash, &property_cmp);
+    if (prop_names == NULL)
+        return 0;
+
+    prop_values = lh_PROPERTY_STRING_new(&property_hash, &property_cmp);
+    if (prop_values == NULL)
+        goto err;
+    return 1;
+
+err:
+    ossl_property_string_cleanup();
+    return 0;
+}
+
+void ossl_property_string_cleanup(void)
+{
+    property_table_free(&prop_names);
+    property_table_free(&prop_values);
+    prop_name_idx = prop_value_idx = 0;
+}
index 796d35e..5bcdbc5 100644 (file)
@@ -187,7 +187,7 @@ int OPENSSL_SA_set(OPENSSL_SA *sa, size_t posn, void *val)
     if (sa == NULL)
         return 0;
 
-    for (level = 1; level <= SA_BLOCK_MAX_LEVELS; level++)
+    for (level = 1; level < SA_BLOCK_MAX_LEVELS; level++)
         if ((n >>= OPENSSL_SA_BLOCK_BITS) == 0)
             break;
 
diff --git a/doc/internal/man3/OSSL_METHOD_STORE.pod b/doc/internal/man3/OSSL_METHOD_STORE.pod
new file mode 100644 (file)
index 0000000..36d26bc
--- /dev/null
@@ -0,0 +1,103 @@
+=pod
+
+=head1 NAME
+
+ossl_method_store_new, ossl_method_store_free, ossl_method_store_init,
+ossl_method_store_cleanup, ossl_method_store_add, ossl_method_store_remove,
+ossl_method_store_fetch, ossl_method_store_set_global_properties,
+ossl_method_store_cache_get and ossl_method_store_cache_set
+- implementation method store and query
+
+=head1 SYNOPSIS
+
+ #include "internal/property.h"
+
+ typedef struct ossl_method_store_st OSSL_METHOD_STORE;
+
+ OSSL_METHOD_STORE *ossl_method_store_new(void);
+ void ossl_method_store_free(OSSL_METHOD_STORE *store);
+ int ossl_method_store_init(void);
+ void ossl_method_store_cleanup(void);
+ int ossl_method_store_add(OSSL_METHOD_STORE *store,
+                           int nid, const char *properties,
+                           void *implementation,
+                           void (*implementation_destruct)(void *));
+ int ossl_method_store_remove(OSSL_METHOD_STORE *store,
+                              int nid, const void *implementation);
+ int ossl_method_store_fetch(OSSL_METHOD_STORE *store,
+                             int nid, const char *properties,
+                             void **result);
+ int ossl_method_store_set_global_properties(OSSL_METHOD_STORE *store,
+                                            const char *prop_query);
+ int ossl_method_store_cache_get(OSSL_METHOD_STORE *store, int nid,
+                                 const char *prop_query, void **result);
+ int ossl_method_store_cache_set(OSSL_METHOD_STORE *store, int nid,
+                                 const char *prop_query, void *result);
+
+=head1 DESCRIPTION
+
+OSSL_METHOD_STORE stores implementations of algorithms that can be queried using
+properties and a NID.
+
+ossl_method_store_init() initialises the implementation method store subsystem.
+
+ossl_method_store_cleanup() cleans up and shuts down the implementation method
+store subsystem
+
+ossl_method_store_new() create a new empty implementation method store.
+
+ossl_method_store_free() frees resources allocated to B<store>.
+
+ossl_method_store_add() adds the B<implementation> to the B<store> as an
+instance of the algorithm indicated by B<nid> and the property definition
+<properties>.
+The optional B<implementation_destruct> function is called when
+B<implementation> is being released from B<store>.
+
+ossl_method_store_remove() remove the B<implementation> of algorithm B<nid>
+from the B<store>.
+
+ossl_method_store_fetch() query B<store> for an implementation of algorithm
+B<nid> that matches the property query B<prop_query>.
+The result, if any, is returned in B<result>.
+
+ossl_method_store_set_global_properties() sets implementation method B<store>
+wide query properties to B<prop_query>.
+All subsequent fetches will need to meet both these global query properties
+and the ones passed to the fetch function.
+
+ossl_method_store_cache_get() queries the cache associated with the B<store>
+for an implementation of algorithm B<nid> that matches the property query
+B<prop_query>.
+The result, if any, is returned in B<result>.
+
+ossl_method_store_cache_set() sets a cache entry for algorithm B<nid> with the
+property query B<prop_query> in the B<store>.
+Future cache gets will return the specified <result>.
+
+=head1 RETURN VALUES
+
+ossl_method_store_new() a new method store object or B<NULL> on failure.
+
+ossl_method_store_free(), ossl_method_store_add(),
+ossl_method_store_remove(), ossl_method_store_fetch(),
+ossl_method_store_set_global_properties(), ossl_method_store_cache_get()
+and ossl_method_store_cache_set() return B<1> on success and B<0> on error.
+
+ossl_method_store_free() and ossl_method_store_cleanup() do not return values.
+
+=head1 HISTORY
+
+This functionality was added to OpenSSL 3.0.0.
+
+=head1 COPYRIGHT
+
+Copyright 2019 The OpenSSL Project Authors. All Rights Reserved.
+Copyright (c) 2019, Oracle and/or its affiliates.  All rights reserved.
+
+Licensed under the Apache License 2.0 (the "License").  You may not use this
+file except in compliance with the License.  You can obtain a copy in the file
+LICENSE in the source distribution or at
+L<https://www.openssl.org/source/license.html>.
+
+=cut
index 7caf9b3..9a927f8 100644 (file)
@@ -6,7 +6,7 @@ LHASH, DECLARE_LHASH_OF,
 OPENSSL_LH_COMPFUNC, OPENSSL_LH_HASHFUNC, OPENSSL_LH_DOALL_FUNC,
 LHASH_DOALL_ARG_FN_TYPE,
 IMPLEMENT_LHASH_HASH_FN, IMPLEMENT_LHASH_COMP_FN,
-lh_TYPE_new, lh_TYPE_free,
+lh_TYPE_new, lh_TYPE_free, lh_TYPE_flush,
 lh_TYPE_insert, lh_TYPE_delete, lh_TYPE_retrieve,
 lh_TYPE_doall, lh_TYPE_doall_arg, lh_TYPE_error - dynamic hash table
 
@@ -20,6 +20,7 @@ lh_TYPE_doall, lh_TYPE_doall_arg, lh_TYPE_error - dynamic hash table
 
  LHASH *lh_TYPE_new(OPENSSL_LH_HASHFUNC hash, OPENSSL_LH_COMPFUNC compare);
  void lh_TYPE_free(LHASH_OF(TYPE) *table);
+ void lh_TYPE_flush(LHASH_OF(TYPE) *table);
 
  TYPE *lh_TYPE_insert(LHASH_OF(TYPE) *table, TYPE *data);
  TYPE *lh_TYPE_delete(LHASH_OF(TYPE) *table, TYPE *data);
@@ -95,6 +96,11 @@ B<table>. Allocated hash table entries will not be freed; consider
 using lh_TYPE_doall() to deallocate any remaining entries in the
 hash table (see below).
 
+lh_TYPE_flush() empties the B<LHASH_OF(TYPE)> structure B<table>. New
+entries can be added to the flushed table.  Allocated hash table entries
+will not be freed; consider using lh_TYPE_doall() to deallocate any
+remaining entries in the hash table (see below).
+
 lh_TYPE_insert() inserts the structure pointed to by B<data> into
 B<table>.  If there already is an entry with the same key, the old
 value is replaced. Note that lh_TYPE_insert() stores pointers, the
@@ -173,7 +179,8 @@ B<NULL> otherwise.
 lh_TYPE_error() returns 1 if an error occurred in the last operation, 0
 otherwise. It's meaningful only after non-retrieve operations.
 
-lh_TYPE_free(), lh_TYPE_doall() and lh_TYPE_doall_arg() return no values.
+lh_TYPE_free(), lh_TYPE_flush, lh_TYPE_doall() and lh_TYPE_doall_arg()
+return no values.
 
 =head1 NOTE
 
diff --git a/include/internal/property.h b/include/internal/property.h
new file mode 100644 (file)
index 0000000..82b3a33
--- /dev/null
@@ -0,0 +1,35 @@
+/*
+ * Copyright 2019 The OpenSSL Project Authors. All Rights Reserved.
+ * Copyright (c) 2019, Oracle and/or its affiliates.  All rights reserved.
+ *
+ * Licensed under the Apache License 2.0 (the "License").  You may not use
+ * this file except in compliance with the License.  You can obtain a copy
+ * in the file LICENSE in the source distribution or at
+ * https://www.openssl.org/source/license.html
+ */
+
+#ifndef HEADER_PROPERTY_H
+# define HEADER_PROPERTY_H
+
+typedef struct ossl_method_store_st OSSL_METHOD_STORE;
+
+/* Implementation store functions */
+OSSL_METHOD_STORE *ossl_method_store_new(void);
+void ossl_method_store_free(OSSL_METHOD_STORE *store);
+int ossl_method_store_add(OSSL_METHOD_STORE *store, int nid,
+                          const char *properties, void *implementation,
+                          void (*implementation_destruct)(void *));
+int ossl_method_store_remove(OSSL_METHOD_STORE *store,
+                             int nid, const void *implementation);
+int ossl_method_store_fetch(OSSL_METHOD_STORE *store, int nid,
+                            const char *prop_query, void **result);
+int ossl_method_store_set_global_properties(OSSL_METHOD_STORE *store,
+                                            const char *prop_query);
+
+/* proeprty query cache functions */
+int ossl_method_store_cache_get(OSSL_METHOD_STORE *store, int nid,
+                                const char *prop_query, void **result);
+int ossl_method_store_cache_set(OSSL_METHOD_STORE *store, int nid,
+                                const char *prop_query, void *result);
+
+#endif
index ed3a2f0..0d6956c 100644 (file)
@@ -95,6 +95,7 @@ typedef struct err_state_st {
 # define ERR_LIB_KDF             52
 # define ERR_LIB_SM2             53
 # define ERR_LIB_ESS             54
+# define ERR_LIB_PROP            55
 
 # define ERR_LIB_USER            128
 
@@ -135,6 +136,7 @@ typedef struct err_state_st {
 # define KDFerr(f,r) ERR_PUT_error(ERR_LIB_KDF,(f),(r),OPENSSL_FILE,OPENSSL_LINE)
 # define SM2err(f,r) ERR_PUT_error(ERR_LIB_SM2,(f),(r),OPENSSL_FILE,OPENSSL_LINE)
 # define ESSerr(f,r) ERR_PUT_error(ERR_LIB_ESS,(f),(r),OPENSSL_FILE,OPENSSL_LINE)
+# define PROPerr(f,r) ERR_PUT_error(ERR_LIB_PROP,(f),(r),OPENSSL_FILE,OPENSSL_LINE)
 
 # define ERR_PACK(l,f,r) ( \
         (((unsigned int)(l) & 0x0FF) << 24L) | \
index cb52d2a..6144fdd 100644 (file)
@@ -72,6 +72,7 @@ typedef struct lhash_st OPENSSL_LHASH;
 int OPENSSL_LH_error(OPENSSL_LHASH *lh);
 OPENSSL_LHASH *OPENSSL_LH_new(OPENSSL_LH_HASHFUNC h, OPENSSL_LH_COMPFUNC c);
 void OPENSSL_LH_free(OPENSSL_LHASH *lh);
+void OPENSSL_LH_flush(OPENSSL_LHASH *lh);
 void *OPENSSL_LH_insert(OPENSSL_LHASH *lh, void *data);
 void *OPENSSL_LH_delete(OPENSSL_LHASH *lh, const void *data);
 void *OPENSSL_LH_retrieve(OPENSSL_LHASH *lh, const void *data);
@@ -131,6 +132,10 @@ void OPENSSL_LH_node_usage_stats_bio(const OPENSSL_LHASH *lh, BIO *out);
     { \
         OPENSSL_LH_free((OPENSSL_LHASH *)lh); \
     } \
+    static ossl_unused ossl_inline void lh_##type##_flush(LHASH_OF(type) *lh) \
+    { \
+        OPENSSL_LH_flush((OPENSSL_LHASH *)lh); \
+    } \
     static ossl_unused ossl_inline type *lh_##type##_insert(LHASH_OF(type) *lh, type *d) \
     { \
         return (type *)OPENSSL_LH_insert((OPENSSL_LHASH *)lh, d); \
index 16cb94b..638b3af 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright 1995-2017 The OpenSSL Project Authors. All Rights Reserved.
+ * Copyright 1995-2019 The OpenSSL Project Authors. All Rights Reserved.
  *
  * Licensed under the Apache License 2.0 (the "License").  You may not use
  * this file except in compliance with the License.  You can obtain a copy
index af8429b..db4e1a7 100644 (file)
@@ -442,7 +442,7 @@ IF[{- !$disabled{tests} -}]
   IF[1]
     PROGRAMS{noinst}=asn1_internal_test modes_internal_test x509_internal_test \
                      tls13encryptiontest wpackettest ctype_internal_test \
-                     rdrand_sanitytest
+                     rdrand_sanitytest property_test
     IF[{- !$disabled{poly1305} -}]
       PROGRAMS{noinst}=poly1305_internal_test
     ENDIF
@@ -490,6 +490,10 @@ IF[{- !$disabled{tests} -}]
     INCLUDE[wpackettest]=../include ../apps/include
     DEPEND[wpackettest]=../libcrypto ../libssl.a libtestutil.a
 
+    SOURCE[property_test]=property_test.c
+    INCLUDE[property_test]=../include ../apps/include
+    DEPEND[property_test]=../libcrypto.a libtestutil.a
+
     SOURCE[ctype_internal_test]=ctype_internal_test.c
     INCLUDE[ctype_internal_test]=.. ../crypto/include ../include ../apps/include
     DEPEND[ctype_internal_test]=../libcrypto.a libtestutil.a
diff --git a/test/property_test.c b/test/property_test.c
new file mode 100644 (file)
index 0000000..ac1a8f7
--- /dev/null
@@ -0,0 +1,374 @@
+/*
+ * Copyright 2019 The OpenSSL Project Authors. All Rights Reserved.
+ * Copyright (c) 2019, Oracle and/or its affiliates.  All rights reserved.
+ *
+ * Licensed under the Apache License 2.0 (the "License").  You may not use
+ * this file except in compliance with the License.  You can obtain a copy
+ * in the file LICENSE in the source distribution or at
+ * https://www.openssl.org/source/license.html
+ */
+
+#include <stdarg.h>
+#include "testutil.h"
+#include "internal/nelem.h"
+#include "internal/property.h"
+#include "../crypto/property/property_lcl.h"
+
+static int add_property_names(const char *n, ...)
+{
+    va_list args;
+    int res = 1;
+
+    va_start(args, n);
+    do {
+        if (!TEST_int_ne(ossl_property_name(n, 1), 0))
+            res = 0;
+    } while ((n = va_arg(args, const char *)) != NULL);
+    va_end(args);
+    return res;
+}
+
+static int test_property_string(void)
+{
+    OSSL_METHOD_STORE *store;
+    int res = 0;
+    OSSL_PROPERTY_IDX i, j;
+
+    if (TEST_ptr(store = ossl_method_store_new())
+        && TEST_int_eq(ossl_property_name("fnord", 0), 0)
+        && TEST_int_ne(ossl_property_name("fnord", 1), 0)
+        && TEST_int_ne(ossl_property_name("name", 1), 0)
+        /* Property value checks */
+        && TEST_int_eq(ossl_property_value("fnord", 0), 0)
+        && TEST_int_ne(i = ossl_property_value("no", 0), 0)
+        && TEST_int_ne(j = ossl_property_value("yes", 0), 0)
+        && TEST_int_ne(i, j)
+        && TEST_int_eq(ossl_property_value("yes", 1), j)
+        && TEST_int_eq(ossl_property_value("no", 1), i)
+        && TEST_int_ne(i = ossl_property_value("green", 1), 0)
+        && TEST_int_eq(j = ossl_property_value("fnord", 1), i + 1)
+        && TEST_int_eq(ossl_property_value("fnord", 1), j)
+        /* Check name and values are distinct */
+        && TEST_int_eq(ossl_property_value("cold", 0), 0)
+        && TEST_int_ne(ossl_property_name("fnord", 0),
+                       ossl_property_value("fnord", 0)))
+        res = 1;
+    ossl_method_store_free(store);
+    return res;
+}
+
+static const struct {
+    const char *defn;
+    const char *query;
+    int e;
+} parser_tests[] = {
+    { "", "sky=blue", 0 },
+    { "", "sky!=blue", 1 },
+    { "groan", "", 1 },
+    { "cold=yes", "cold=yes", 1 },
+    { "cold=yes", "cold", 1 },
+    { "cold=yes", "cold!=no", 1 },
+    { "groan", "groan=yes", 1 },
+    { "groan", "groan=no", 0 },
+    { "groan", "groan!=yes", 0 },
+    { "cold=no", "cold", 0 },
+    { "cold=no", "cold=no", 1 },
+    { "groan", "cold", 0 },
+    { "groan", "cold=no", 1 },
+    { "groan", "cold!=yes", 1 },
+    { "groan=blue", "groan=yellow", 0 },
+    { "groan=blue", "groan!=yellow", 1 },
+    { "today=monday, tomorrow=3", "today!=2", 1 },
+    { "today=monday, tomorrow=3", "today!='monday'", 0 },
+    { "today=monday, tomorrow=3", "tomorrow=3", 1 },
+    { "n=0x3", "n=3", 1 },
+    { "n=0x3", "n=-3", 0 },
+    { "n=0x33", "n=51", 1 },
+    { "n=033", "n=27", 1 },
+    { "n=0", "n=00", 1 },
+    { "n=0x0", "n=0", 1 },
+};
+
+static int test_property_parse(int n)
+{
+    OSSL_METHOD_STORE *store;
+    OSSL_PROPERTY_LIST *p = NULL, *q = NULL;
+    int r = 0;
+
+    if (TEST_ptr(store = ossl_method_store_new())
+        && add_property_names("sky", "groan", "cold", "today", "tomorrow", "n",
+                              NULL)
+        && TEST_ptr(p = ossl_parse_property(parser_tests[n].defn))
+        && TEST_ptr(q = ossl_parse_query(parser_tests[n].query))
+        && TEST_int_eq(ossl_property_match(q, p), parser_tests[n].e))
+        r = 1;
+    ossl_property_free(p);
+    ossl_property_free(q);
+    ossl_method_store_free(store);
+    return r;
+}
+
+static const struct {
+    const char *q_global;
+    const char *q_local;
+    const char *prop;
+} merge_tests[] = {
+    { "", "colour=blue", "colour=blue" },
+    { "colour=blue", "", "colour=blue" },
+    { "colour=red", "colour=blue", "colour=blue" },
+    { "clouds=pink, urn=red", "urn=blue, colour=green",
+        "urn=blue, colour=green, clouds=pink" },
+    { "pot=gold", "urn=blue", "pot=gold, urn=blue" },
+    { "night", "day", "day=yes, night=yes" },
+    { "day", "night", "day=yes, night=yes" },
+    { "", "", "" },
+    /*
+     * The following four leave 'day' unspecified in the query, and will match
+     * any definition
+     */
+    { "day=yes", "-day", "day=no" },
+    { "day=yes", "-day", "day=yes" },
+    { "day=yes", "-day", "day=arglebargle" },
+    { "day=yes", "-day", "pot=sesquioxidizing" },
+    { "day, night", "-night, day", "day=yes, night=no" },
+    { "-day", "day=yes", "day=yes" },
+};
+
+static int test_property_merge(int n)
+{
+    OSSL_METHOD_STORE *store;
+    OSSL_PROPERTY_LIST *q_global = NULL, *q_local = NULL;
+    OSSL_PROPERTY_LIST *q_combined = NULL, *prop = NULL;
+    int r = 0;
+
+    if (TEST_ptr(store = ossl_method_store_new())
+        && add_property_names("colour", "urn", "clouds", "pot", "day", "night",
+                              NULL)
+        && TEST_ptr(prop = ossl_parse_property(merge_tests[n].prop))
+        && TEST_ptr(q_global = ossl_parse_query(merge_tests[n].q_global))
+        && TEST_ptr(q_local = ossl_parse_query(merge_tests[n].q_local))
+        && TEST_ptr(q_combined = ossl_property_merge(q_local, q_global))
+        && TEST_true(ossl_property_match(q_combined, prop)))
+        r = 1;
+    ossl_property_free(q_global);
+    ossl_property_free(q_local);
+    ossl_property_free(q_combined);
+    ossl_property_free(prop);
+    ossl_method_store_free(store);
+    return r;
+}
+
+static int test_property_defn_cache(void)
+{
+    OSSL_METHOD_STORE *store;
+    OSSL_PROPERTY_LIST *red, *blue;
+    int r = 0;
+
+    if (TEST_ptr(store = ossl_method_store_new())
+        && add_property_names("red", "blue", NULL)
+        && TEST_ptr(red = ossl_parse_property("red"))
+        && TEST_ptr(blue = ossl_parse_property("blue"))
+        && TEST_ptr_ne(red, blue)
+        && TEST_true(ossl_prop_defn_set("red", red))
+        && TEST_true(ossl_prop_defn_set("blue", blue))
+        && TEST_ptr_eq(ossl_prop_defn_get("red"), red)
+        && TEST_ptr_eq(ossl_prop_defn_get("blue"), blue))
+        r = 1;
+    ossl_method_store_free(store);
+    return r;
+}
+
+static const struct {
+    const char *defn;
+    const char *query;
+    int e;
+} definition_tests[] = {
+    { "alpha", "alpha=yes", 1 },
+    { "alpha=no", "alpha", 0 },
+    { "alpha=1", "alpha=1", 1 },
+    { "alpha=2", "alpha=1", 0 },
+    { "alpha", "omega", 0 }
+};
+
+static int test_definition_compares(int n)
+{
+    OSSL_METHOD_STORE *store;
+    OSSL_PROPERTY_LIST *d = NULL, *q = NULL;
+    int r;
+
+    r = TEST_ptr(store = ossl_method_store_new())
+        && add_property_names("alpha", "omega", NULL)
+        && TEST_ptr(d = ossl_parse_property(definition_tests[n].defn))
+        && TEST_ptr(q = ossl_parse_query(definition_tests[n].query))
+        && TEST_int_eq(ossl_property_match(q, d), definition_tests[n].e);
+
+    ossl_property_free(d);
+    ossl_property_free(q);
+    ossl_method_store_free(store);
+    return r;
+}
+
+static int test_register_deregister(void)
+{
+    static const struct {
+        int nid;
+        const char *prop;
+        char *impl;
+    } impls[] = {
+        { 6, "position=1", "a" },
+        { 6, "position=2", "b" },
+        { 6, "position=3", "c" },
+        { 6, "position=4", "d" },
+    };
+    size_t i;
+    int ret = 0;
+    OSSL_METHOD_STORE *store;
+
+    if (!TEST_ptr(store = ossl_method_store_new())
+        || !add_property_names("position", NULL))
+        goto err;
+
+    for (i = 0; i < OSSL_NELEM(impls); i++)
+        if (!TEST_true(ossl_method_store_add(store, impls[i].nid, impls[i].prop,
+                                             impls[i].impl, NULL))) {
+            TEST_note("iteration %zd", i + 1);
+            goto err;
+        }
+
+    /* Deregister in a different order to registration */
+    for (i = 0; i < OSSL_NELEM(impls); i++) {
+        const size_t j = (1 + i * 3) % OSSL_NELEM(impls);
+        int nid = impls[j].nid;
+        void *impl = impls[j].impl;
+
+        if (!TEST_true(ossl_method_store_remove(store, nid, impl))
+            || !TEST_false(ossl_method_store_remove(store, nid, impl))) {
+            TEST_note("iteration %zd, position %zd", i + 1, j + 1);
+            goto err;
+        }
+    }
+
+    if (TEST_false(ossl_method_store_remove(store, impls[0].nid, impls[0].impl)))
+        ret = 1;
+err:
+    ossl_method_store_free(store);
+    return ret;
+}
+
+static int test_property(void)
+{
+    static const struct {
+        int nid;
+        const char *prop;
+        char *impl;
+    } impls[] = {
+        { 1, "fast=no, colour=green", "a" },
+        { 1, "fast, colour=blue", "b" },
+        { 1, "", "-" },
+        { 9, "sky=blue, furry", "c" },
+        { 3, NULL, "d" },
+        { 6, "sky.colour=blue, sky=green, old.data", "e" },
+    };
+    static struct {
+        int nid;
+        const char *prop;
+        char *expected;
+    } queries[] = {
+        { 1, "fast", "b" },
+        { 1, "fast=yes", "b" },
+        { 1, "fast=no, colour=green", "a" },
+        { 1, "colour=blue, fast", "b" },
+        { 1, "colour=blue", "b" },
+        { 9, "furry", "c" },
+        { 6, "sky.colour=blue", "e" },
+        { 6, "old.data", "e" },
+        { 9, "furry=yes, sky=blue", "c" },
+        { 1, "", "a" },
+        { 3, "", "d" },
+    };
+    OSSL_METHOD_STORE *store;
+    size_t i;
+    int ret = 0;
+    void *result;
+
+    if (!TEST_ptr(store = ossl_method_store_new())
+        || !add_property_names("fast", "colour", "sky", "furry", NULL))
+        goto err;
+
+    for (i = 0; i < OSSL_NELEM(impls); i++)
+        if (!TEST_true(ossl_method_store_add(store, impls[i].nid, impls[i].prop,
+                                             impls[i].impl, NULL))) {
+            TEST_note("iteration %zd", i + 1);
+            goto err;
+        }
+    for (i = 0; i < OSSL_NELEM(queries); i++) {
+        OSSL_PROPERTY_LIST *pq = NULL;
+
+        if (!TEST_true(ossl_property_read_lock(store))
+            || !TEST_true(ossl_method_store_fetch(store, queries[i].nid,
+                                                  queries[i].prop, &result))
+            || !TEST_true(ossl_property_unlock(store))
+            || !TEST_str_eq((char *)result, queries[i].expected)) {
+            TEST_note("iteration %zd", i + 1);
+            ossl_property_free(pq);
+            goto err;
+        }
+        ossl_property_free(pq);
+    }
+    ret = 1;
+err:
+    ossl_method_store_free(store);
+    return ret;
+}
+
+static int test_query_cache_stochastic(void)
+{
+    const int max = 10000, tail = 10;
+    OSSL_METHOD_STORE *store;
+    int i, res = 0;
+    char buf[50];
+    void *result;
+    int errors = 0;
+    int v[10001];
+
+    if (!TEST_ptr(store = ossl_method_store_new())
+        || !add_property_names("n", NULL))
+        goto err;
+
+    for (i = 1; i <= max; i++) {
+        v[i] = 2 * i;
+        BIO_snprintf(buf, sizeof(buf), "n=%d\n", i);
+        if (!TEST_true(ossl_method_store_add(store, i, buf, "abc", NULL))
+                || !TEST_true(ossl_method_store_cache_set(store, i, buf, v + i))
+                || !TEST_true(ossl_method_store_cache_set(store, i, "n=1234",
+                                                          "miss"))) {
+            TEST_note("iteration %d", i);
+            goto err;
+        }
+    }
+    for (i = 1; i <= max; i++) {
+        BIO_snprintf(buf, sizeof(buf), "n=%d\n", i);
+        if (!ossl_method_store_cache_get(store, i, buf, &result)
+            || result != v + i)
+            errors++;
+    }
+    /* There is a tiny probability that this will fail when it shouldn't */
+    res = TEST_int_gt(errors, tail) && TEST_int_lt(errors, max - tail);
+
+err:
+    ossl_method_store_free(store);
+    return res;
+}
+
+int setup_tests(void)
+{
+    ADD_TEST(test_property_string);
+    ADD_ALL_TESTS(test_property_parse, OSSL_NELEM(parser_tests));
+    ADD_ALL_TESTS(test_property_merge, OSSL_NELEM(merge_tests));
+    ADD_TEST(test_property_defn_cache);
+    ADD_ALL_TESTS(test_definition_compares, OSSL_NELEM(definition_tests));
+    ADD_TEST(test_register_deregister);
+    ADD_TEST(test_property);
+    ADD_TEST(test_query_cache_stochastic);
+    return 1;
+}
diff --git a/test/recipes/03-test_property.t b/test/recipes/03-test_property.t
new file mode 100644 (file)
index 0000000..2654215
--- /dev/null
@@ -0,0 +1,12 @@
+#! /usr/bin/env perl
+# Copyright 2019 The OpenSSL Project Authors. All Rights Reserved.
+# Copyright (c) 2019, Oracle and/or its affiliates.  All rights reserved.
+#
+# Licensed under the Apache License 2.0 (the "License").  You may not use
+# this file except in compliance with the License.  You can obtain a copy
+# in the file LICENSE in the source distribution or at
+# https://www.openssl.org/source/license.html
+
+use OpenSSL::Test::Simple;
+
+simple_test("test_property", "property_test");
index fa57f3f..02ce0d1 100644 (file)
@@ -164,7 +164,7 @@ static int test_sparse_array_doall(void)
             TEST_note("failed at iteration %zu", i + 1);
             goto err;
     }
-    
+
     ossl_sa_char_doall_arg(sa, &leaf_check_all, &doall_data);
     if (doall_data.res == 0) {
         TEST_info("while checking all elements");