Randall S. Becker 4a9e48f727 Correct OSSL_sleep for NonStop PUT model by introducing sleep(). 6 days ago
..
aes ed0f79c7ae Fix a few incorrect paths in some build.info files 1 month ago
aria 36c269c302 Change loops conditions to make zero loop risk more obvious. 1 year ago
asn1 eadd8c4727 Add appropriate lower bound checks for GeneralizedTime and UTCTime 1 month ago
async e077455e9e Stop raising ERR_R_MALLOC_FAILURE in most places 1 year ago
bf f6a6f7b6aa Avoid duplicating symbols in legacy.a with some build options 1 year ago
bio 24109dca5a Don’t use the recvmmsg dgram method on Android <5 5 days ago
bn 9c1b8f17ce Avoid an infinite loop in BN_GF2m_mod_inv 3 months ago
buffer e077455e9e Stop raising ERR_R_MALLOC_FAILURE in most places 1 year ago
camellia 9968c77539 Rename x86-32 assembly files from .s to .S. 1 year ago
cast da1c088f59 Copyright year updates 6 months ago
chacha 1afb326da4 chachap10-ppc.pl: Fix truncated relocation 1 month ago
cmac 6f22bcd631 Add appropriate NULL checks in EVP_CIPHER api 2 months ago
cmp bcd3707dba crypto/cmp: add OSSL_CMP_MSG_get0_certreq_publickey(); fix coding style nit 3 weeks ago
cms 6f22bcd631 Add appropriate NULL checks in EVP_CIPHER api 2 months ago
comp da1c088f59 Copyright year updates 6 months ago
conf 707b54bee2 plug potential memory leak in error code path 1 week ago
crmf da1c088f59 Copyright year updates 6 months ago
ct e077455e9e Stop raising ERR_R_MALLOC_FAILURE in most places 1 year ago
des da1c088f59 Copyright year updates 6 months ago
dh de61dba390 Fix typos 2 months ago
dsa de61dba390 Fix typos 2 months ago
dso 0f644b96d2 replace strstr() with strchr() for single characters 2 months ago
ec e5313f2048 OpenSSL License is applied for some source files, change to Apache 2 1 month ago
encode_decode cf57c3ecfa Check for NULL cleanup function before using it in encoder_process 1 month ago
engine 39ea783798 Revert "Improved detection of engine-provided private "classic" keys" 1 month ago
err 7f8aba2f44 Limit the number of http headers when receiving the http response 2 weeks ago
ess e077455e9e Stop raising ERR_R_MALLOC_FAILURE in most places 1 year ago
evp dc9bc6c8e1 Fix unbounded memory growth when using no-cached-fetch 1 week ago
ffc eaee1765a4 DH_check_pub_key() should not fail when setting result code 5 months ago
hmac 21dfdbef49 Adapt other parts of the source to the changed EVP_Q_digest() and EVP_Q_mac() 2 years ago
hpke e5313f2048 OpenSSL License is applied for some source files, change to Apache 2 1 month ago
http 7f8aba2f44 Limit the number of http headers when receiving the http response 2 weeks ago
idea f6a6f7b6aa Avoid duplicating symbols in legacy.a with some build options 1 year ago
kdf 905b097fd5 Deprecate ERR_load_KDF_strings() 4 years ago
lhash 5c42ced0ff Introduce hash thunking functions to do proper casting 2 months ago
md2 f6a6f7b6aa Avoid duplicating symbols in legacy.a with some build options 1 year ago
md4 f6a6f7b6aa Avoid duplicating symbols in legacy.a with some build options 1 year ago
md5 3d68e2937e md5: add assembly implementation for loongarch64 3 months ago
mdc2 f6a6f7b6aa Avoid duplicating symbols in legacy.a with some build options 1 year ago
modes df04e81794 aes_platform.h, gcm128.c: fix Darwin PowerPC macro to include ppc64 2 months ago
objects c5e097dec5 Add Content Type OID for id-ct-rpkiSignedPrefixList 1 week ago
ocsp da1c088f59 Copyright year updates 6 months ago
pem 556009c596 Copyright year updates 6 months ago
perlasm 1da7c09f79 x86_64-xlate.pl: Fix build with icx and nvc compilers 4 months ago
pkcs12 041962b429 Add NULL checks where ContentInfo data can be NULL 2 months ago
pkcs7 8211ca45e4 PKCS7: Remove one of the duplicate checks 2 weeks ago
poly1305 7068e5e2dc poly1305_ieee754.c: fix PowerPC macros 2 months ago
property c3e8d67885 Fixed Visual Studio 2008 compiler errors 1 month ago
rand f1e0c94545 internal/common.h: rename macro `(un)likely` to `ossl_(un)likely` 4 months ago
rc2 da1c088f59 Copyright year updates 6 months ago
rc4 da1c088f59 Copyright year updates 6 months ago
rc5 da1c088f59 Copyright year updates 6 months ago
ripemd f6a6f7b6aa Avoid duplicating symbols in legacy.a with some build options 1 year ago
rsa e09fc1d746 Limit the execution time of RSA public key check 2 months ago
seed f6a6f7b6aa Avoid duplicating symbols in legacy.a with some build options 1 year ago
sha ed0f79c7ae Fix a few incorrect paths in some build.info files 1 month ago
siphash c734058309 crypto/*: Fix various typos, repeated words, align some spelling to LDP. 1 year ago
sm2 9170cc0398 Optimize the implementation of ec_field_size() 1 month ago
sm3 1c25bc2e3f riscv: Support sm3 on platforms with vlen >= 128. 5 months ago
sm4 2a2561709a Fix sm4-xts aarch64 assembly implementation bug 1 month ago
srp 556009c596 Copyright year updates 6 months ago
stack 98d6016afe Make OPENSSL_sk_push return only 0 or 1 2 months ago
store 556009c596 Copyright year updates 6 months ago
thread da1c088f59 Copyright year updates 6 months ago
ts da1c088f59 Copyright year updates 6 months ago
txt_db da1c088f59 Copyright year updates 6 months ago
ui da1c088f59 Copyright year updates 6 months ago
whrlpool da1c088f59 Copyright year updates 6 months ago
x509 6134e8e6dd Fix a memory leak on successful load of CRL 2 weeks ago
LPdir_nyi.c 0e9725bcb9 Following the license change, modify the boilerplates in crypto/ 5 years ago
LPdir_unix.c da1c088f59 Copyright year updates 6 months ago
LPdir_vms.c 0e9725bcb9 Following the license change, modify the boilerplates in crypto/ 5 years ago
LPdir_win.c 0e9725bcb9 Following the license change, modify the boilerplates in crypto/ 5 years ago
LPdir_win32.c 0e9725bcb9 Following the license change, modify the boilerplates in crypto/ 5 years ago
LPdir_wince.c 0e9725bcb9 Following the license change, modify the boilerplates in crypto/ 5 years ago
README-sparse_array.md 1dc1ea182b Fix many MarkDown issues in {NOTES*,README*,HACKING,LICENSE}.md files 3 years ago
alphacpuid.pl 33388b44b6 Update copyright year 3 years ago
arm64cpuid.pl fecb3aae22 Update copyright year 1 year ago
arm_arch.h 11adf9a75d Apply the AES-GCM unroll8 optimisation to Microsoft Azure Cobalt 100 1 month ago
armcap.c 11adf9a75d Apply the AES-GCM unroll8 optimisation to Microsoft Azure Cobalt 100 1 month ago
armv4cpuid.pl da1c088f59 Copyright year updates 6 months ago
asn1_dsa.c 3c2bdd7df9 Update copyright year 3 years ago
bsearch.c 5c3f1e34b5 ossl_bsearch(): New generic internal binary search utility function 4 years ago
build.info 34d36cdcbd Do not include sparse_array.o in libssl 6 months ago
c64xpluscpuid.pl 33388b44b6 Update copyright year 3 years ago
context.c da1c088f59 Copyright year updates 6 months ago
core_algorithm.c e077455e9e Stop raising ERR_R_MALLOC_FAILURE in most places 1 year ago
core_fetch.c e1eafe8c87 "Reserve" the method store when constructing methods 1 year ago
core_namemap.c da1c088f59 Copyright year updates 6 months ago
cpt_err.c 826da1451b err: add additional errors 2 years ago
cpuid.c 556009c596 Copyright year updates 6 months ago
cryptlib.c da1c088f59 Copyright year updates 6 months ago
ctype.c da1c088f59 Copyright year updates 6 months ago
cversion.c 26b7cc0d20 Cleanup include/openssl/opensslv.h.in 4 years ago
der_writer.c 59196250cb der_writer: Use uint32_t instead of long. 1 year ago
deterministic_nonce.c da1c088f59 Copyright year updates 6 months ago
dllmain.c fecb3aae22 Update copyright year 1 year ago
ebcdic.c 0e9725bcb9 Following the license change, modify the boilerplates in crypto/ 5 years ago
ex_data.c d4f22a915a Fix error handling in CRYPTO_get_ex_new_index 6 months ago
getenv.c fecb3aae22 Update copyright year 1 year ago
ia64cpuid.S 0e9725bcb9 Following the license change, modify the boilerplates in crypto/ 5 years ago
info.c da1c088f59 Copyright year updates 6 months ago
init.c 99fb31c167 Add atexit configuration option to using atexit() in libcrypto at build-time. 1 month ago
initthread.c c61fda2ff8 crypto/initthread.c: fix misspelled OSSL_provider_init() in comment 5 months ago
loongarch64cpuid.pl a607546e6e LoongArch64 assembly pack: Really implement OPENSSL_rdtsc 3 months ago
loongarch_arch.h da1c088f59 Copyright year updates 6 months ago
loongarchcap.c da1c088f59 Copyright year updates 6 months ago
mem.c 3b107b86ca Windows: use srand() instead of srandom() 5 months ago
mem_clr.c 0e9725bcb9 Following the license change, modify the boilerplates in crypto/ 5 years ago
mem_sec.c 7eae6ee0e5 Add locking to CRYPTO_secure_used 3 months ago
mips_arch.h ae4186b004 Fix header file include guard names 4 years ago
o_dir.c fecb3aae22 Update copyright year 1 year ago
o_fopen.c 1567a821a4 crypto: Fix various typos, repeated words, align some spelling to LDP. 1 year ago
o_init.c fecb3aae22 Update copyright year 1 year ago
o_str.c c5cc9c419a Fix off by one issue in buf2hexstr_sep() 3 weeks ago
o_time.c 8020d79b40 Update copyright year 3 years ago
packet.c da1c088f59 Copyright year updates 6 months ago
param_build.c 5a40a2728a params: drop INT_MAX checks 3 months ago
param_build_set.c 15a39e7025 ossl_param_build_set_multi_key_bn(): Do not set NULL BIGNUMs 5 months ago
params.c 806bbafe2d Check appropriate OSSL_PARAM_get_* functions for NULL 2 months ago
params_dup.c e077455e9e Stop raising ERR_R_MALLOC_FAILURE in most places 1 year ago
params_from_text.c ea6268cfce Have OSSL_PARAM_allocate_from_text() fail on odd number of hex digits 2 months ago
params_idx.c.in e84b5fcc1b params: provide a faster TRIE based param lookup. 10 months ago
pariscid.pl 33388b44b6 Update copyright year 3 years ago
passphrase.c e077455e9e Stop raising ERR_R_MALLOC_FAILURE in most places 1 year ago
ppccap.c fecb3aae22 Update copyright year 1 year ago
ppccpuid.pl fecb3aae22 Update copyright year 1 year ago
provider.c da1c088f59 Copyright year updates 6 months ago
provider_child.c da1c088f59 Copyright year updates 6 months ago
provider_conf.c 9277ed0a4f Fix remaining provider config settings to be decisive in value 3 months ago
provider_core.c 8fa65a6648 After initializing a provider, check if its output dispatch table is NULL 3 months ago
provider_local.h b7248964a4 make struct provider_info_st a full type 2 years ago
provider_predefined.c b7248964a4 make struct provider_info_st a full type 2 years ago
punycode.c da1c088f59 Copyright year updates 6 months ago
quic_vlint.c 6292519cd8 QUIC: Enable building with QUIC support disabled 1 year ago
rcu_internal.h d0e1a0ae70 RCU lock implementation 1 month ago
riscv32cpuid.pl 61170642b1 Add RISC-V 32 cpuid support 1 year ago
riscv64cpuid.pl cdea67193d riscv: Add basic vector extension support 5 months ago
riscvcap.c cdea67193d riscv: Add basic vector extension support 5 months ago
s390x_arch.h da1c088f59 Copyright year updates 6 months ago
s390xcap.c da1c088f59 Copyright year updates 6 months ago
s390xcpuid.pl 33388b44b6 Update copyright year 3 years ago
self_test_core.c fecb3aae22 Update copyright year 1 year ago
sleep.c 4a9e48f727 Correct OSSL_sleep for NonStop PUT model by introducing sleep(). 4 days ago
sparccpuid.S 0e9725bcb9 Following the license change, modify the boilerplates in crypto/ 5 years ago
sparcv9cap.c 52f7e44ec8 Split bignum code out of the sparcv9cap.c 2 years ago
sparse_array.c 93429fc0ce Coverity 1507376: Dereference after null check 1 year ago
threads_lib.c 523e54c15c Define threads_lib.c functions only for OPENSSL_SYS_UNIX 1 year ago
threads_none.c d0e1a0ae70 RCU lock implementation 1 month ago
threads_pthread.c 39fe3e5de1 Fix the grammar as suggsted in the review 1 month ago
threads_win.c d0e1a0ae70 RCU lock implementation 1 month ago
time.c da1c088f59 Copyright year updates 6 months ago
trace.c bbaeadb068 "foo * bar" should be "foo *bar" 6 months ago
uid.c da1c088f59 Copyright year updates 6 months ago
vms_rms.h 0e9725bcb9 Following the license change, modify the boilerplates in crypto/ 5 years ago
x86_64cpuid.pl 3c2bdd7df9 Update copyright year 3 years ago
x86cpuid.pl 33388b44b6 Update copyright year 3 years ago

README-sparse_array.md

Sparse Arrays

The sparse_array.c file contains an implementation of a sparse array that attempts to be both space and time efficient.

The sparse array is represented using a tree structure. Each node in the tree contains a block of pointers to either the user supplied leaf values or to another node.

There are a number of parameters used to define the block size:

OPENSSL_SA_BLOCK_BITS   Specifies the number of bits covered by each block
SA_BLOCK_MAX            Specifies the number of pointers in each block
SA_BLOCK_MASK           Specifies a bit mask to perform modulo block size
SA_BLOCK_MAX_LEVELS     Indicates the maximum possible height of the tree

These constants are inter-related:

SA_BLOCK_MAX        = 2 ^ OPENSSL_SA_BLOCK_BITS
SA_BLOCK_MASK       = SA_BLOCK_MAX - 1
SA_BLOCK_MAX_LEVELS = number of bits in size_t divided by
                      OPENSSL_SA_BLOCK_BITS rounded up to the next multiple
                      of OPENSSL_SA_BLOCK_BITS

OPENSSL_SA_BLOCK_BITS can be defined at compile time and this overrides the built in setting.

As a space and performance optimisation, the height of the tree is usually less than the maximum possible height. Only sufficient height is allocated to accommodate the largest index added to the data structure.

The largest index used to add a value to the array determines the tree height:

    +----------------------+---------------------+
    | Largest Added Index  |   Height of Tree    |
    +----------------------+---------------------+
    | SA_BLOCK_MAX     - 1 |          1          |
    | SA_BLOCK_MAX ^ 2 - 1 |          2          |
    | SA_BLOCK_MAX ^ 3 - 1 |          3          |
    | ...                  |          ...        |
    | size_t max           | SA_BLOCK_MAX_LEVELS |
    +----------------------+---------------------+

The tree height is dynamically increased as needed based on additions.

An empty tree is represented by a NULL root pointer. Inserting a value at index 0 results in the allocation of a top level node full of null pointers except for the single pointer to the user's data (N = SA_BLOCK_MAX for brevity):

    +----+
    |Root|
    |Node|
    +-+--+
      |
      |
      |
      v
    +-+-+---+---+---+---+
    | 0 | 1 | 2 |...|N-1|
    |   |nil|nil|...|nil|
    +-+-+---+---+---+---+
      |
      |
      |
      v
    +-+--+
    |User|
    |Data|
    +----+
Index 0

Inserting at element 2N+1 creates a new root node and pushes down the old root node. It then creates a second second level node to hold the pointer to the user's new data:

    +----+
    |Root|
    |Node|
    +-+--+
      |
      |
      |
      v
    +-+-+---+---+---+---+
    | 0 | 1 | 2 |...|N-1|
    |   |nil|   |...|nil|
    +-+-+---+-+-+---+---+
      |       |
      |       +------------------+
      |                          |
      v                          v
    +-+-+---+---+---+---+      +-+-+---+---+---+---+
    | 0 | 1 | 2 |...|N-1|      | 0 | 1 | 2 |...|N-1|
    |nil|   |nil|...|nil|      |nil|   |nil|...|nil|
    +-+-+---+---+---+---+      +---+-+-+---+---+---+
      |                              |
      |                              |
      |                              |
      v                              v
    +-+--+                         +-+--+
    |User|                         |User|
    |Data|                         |Data|
    +----+                         +----+
Index 0                       Index 2N+1

The nodes themselves are allocated in a sparse manner. Only nodes which exist along a path from the root of the tree to an added leaf will be allocated. The complexity is hidden and nodes are allocated on an as needed basis. Because the data is expected to be sparse this doesn't result in a large waste of space.

Values can be removed from the sparse array by setting their index position to NULL. The data structure does not attempt to reclaim nodes or reduce the height of the tree on removal. For example, now setting index 0 to NULL would result in:

    +----+
    |Root|
    |Node|
    +-+--+
      |
      |
      |
      v
    +-+-+---+---+---+---+
    | 0 | 1 | 2 |...|N-1|
    |   |nil|   |...|nil|
    +-+-+---+-+-+---+---+
      |       |
      |       +------------------+
      |                          |
      v                          v
    +-+-+---+---+---+---+      +-+-+---+---+---+---+
    | 0 | 1 | 2 |...|N-1|      | 0 | 1 | 2 |...|N-1|
    |nil|nil|nil|...|nil|      |nil|   |nil|...|nil|
    +---+---+---+---+---+      +---+-+-+---+---+---+
                                     |
                                     |
                                     |
                                     v
                                   +-+--+
                                   |User|
                                   |Data|
                                   +----+
                              Index 2N+1

Accesses to elements in the sparse array take O(log n) time where n is the largest element. The base of the logarithm is SA_BLOCK_MAX, so for moderately small indices (e.g. NIDs), single level (constant time) access is achievable. Space usage is O(minimum(m, n log(n)) where m is the number of elements in the array.

Note: sparse arrays only include pointers to types. Thus, SPARSE_ARRAY_OF(char) can be used to store a string.