On 10/11/19 9:41 AM, AKASHI Takahiro wrote:
Imported from linux kernel v5.3.
Please, indicate in the commit message which files are verbatim copies and which files had to be adjusted. E.g. in lib/oid_registry.c you adjusted the includes.
Signed-off-by: AKASHI Takahiro takahiro.akashi@linaro.org
include/linux/oid_registry.h | 117 ++++++++++++++++++++ lib/Kconfig | 5 + lib/Makefile | 16 +++ lib/build_OID_registry | 203 +++++++++++++++++++++++++++++++++++
Shouldn't this file go into /scripts or /tools?
Best regards
Heinrich
lib/oid_registry.c | 179 ++++++++++++++++++++++++++++++ 5 files changed, 520 insertions(+) create mode 100644 include/linux/oid_registry.h create mode 100755 lib/build_OID_registry create mode 100644 lib/oid_registry.c
diff --git a/include/linux/oid_registry.h b/include/linux/oid_registry.h new file mode 100644 index 000000000000..657d6bf2c064 --- /dev/null +++ b/include/linux/oid_registry.h @@ -0,0 +1,117 @@ +/* SPDX-License-Identifier: GPL-2.0-or-later */ +/* ASN.1 Object identifier (OID) registry
- Copyright (C) 2012 Red Hat, Inc. All Rights Reserved.
- Written by David Howells (dhowells@redhat.com)
- */
+#ifndef _LINUX_OID_REGISTRY_H +#define _LINUX_OID_REGISTRY_H
+#include <linux/types.h>
+/*
- OIDs are turned into these values if possible, or OID__NR if not held here.
- NOTE! Do not mess with the format of each line as this is read by
build_OID_registry.pl to generate the data for look_up_OID().- */
+enum OID {
- OID_id_dsa_with_sha1, /* 1.2.840.10030.4.3 */
- OID_id_dsa, /* 1.2.840.10040.4.1 */
- OID_id_ecdsa_with_sha1, /* 1.2.840.10045.4.1 */
- OID_id_ecPublicKey, /* 1.2.840.10045.2.1 */
- /* PKCS#1 {iso(1) member-body(2) us(840) rsadsi(113549) pkcs(1) pkcs-1(1)} */
- OID_rsaEncryption, /* 1.2.840.113549.1.1.1 */
- OID_md2WithRSAEncryption, /* 1.2.840.113549.1.1.2 */
- OID_md3WithRSAEncryption, /* 1.2.840.113549.1.1.3 */
- OID_md4WithRSAEncryption, /* 1.2.840.113549.1.1.4 */
- OID_sha1WithRSAEncryption, /* 1.2.840.113549.1.1.5 */
- OID_sha256WithRSAEncryption, /* 1.2.840.113549.1.1.11 */
- OID_sha384WithRSAEncryption, /* 1.2.840.113549.1.1.12 */
- OID_sha512WithRSAEncryption, /* 1.2.840.113549.1.1.13 */
- OID_sha224WithRSAEncryption, /* 1.2.840.113549.1.1.14 */
- /* PKCS#7 {iso(1) member-body(2) us(840) rsadsi(113549) pkcs(1) pkcs-7(7)} */
- OID_data, /* 1.2.840.113549.1.7.1 */
- OID_signed_data, /* 1.2.840.113549.1.7.2 */
- /* PKCS#9 {iso(1) member-body(2) us(840) rsadsi(113549) pkcs(1) pkcs-9(9)} */
- OID_email_address, /* 1.2.840.113549.1.9.1 */
- OID_contentType, /* 1.2.840.113549.1.9.3 */
- OID_messageDigest, /* 1.2.840.113549.1.9.4 */
- OID_signingTime, /* 1.2.840.113549.1.9.5 */
- OID_smimeCapabilites, /* 1.2.840.113549.1.9.15 */
- OID_smimeAuthenticatedAttrs, /* 1.2.840.113549.1.9.16.2.11 */
- /* {iso(1) member-body(2) us(840) rsadsi(113549) digestAlgorithm(2)} */
- OID_md2, /* 1.2.840.113549.2.2 */
- OID_md4, /* 1.2.840.113549.2.4 */
- OID_md5, /* 1.2.840.113549.2.5 */
- /* Microsoft Authenticode & Software Publishing */
- OID_msIndirectData, /* 1.3.6.1.4.1.311.2.1.4 */
- OID_msStatementType, /* 1.3.6.1.4.1.311.2.1.11 */
- OID_msSpOpusInfo, /* 1.3.6.1.4.1.311.2.1.12 */
- OID_msPeImageDataObjId, /* 1.3.6.1.4.1.311.2.1.15 */
- OID_msIndividualSPKeyPurpose, /* 1.3.6.1.4.1.311.2.1.21 */
- OID_msOutlookExpress, /* 1.3.6.1.4.1.311.16.4 */
- OID_certAuthInfoAccess, /* 1.3.6.1.5.5.7.1.1 */
- OID_sha1, /* 1.3.14.3.2.26 */
- OID_sha256, /* 2.16.840.1.101.3.4.2.1 */
- OID_sha384, /* 2.16.840.1.101.3.4.2.2 */
- OID_sha512, /* 2.16.840.1.101.3.4.2.3 */
- OID_sha224, /* 2.16.840.1.101.3.4.2.4 */
- /* Distinguished Name attribute IDs [RFC 2256] */
- OID_commonName, /* 2.5.4.3 */
- OID_surname, /* 2.5.4.4 */
- OID_countryName, /* 2.5.4.6 */
- OID_locality, /* 2.5.4.7 */
- OID_stateOrProvinceName, /* 2.5.4.8 */
- OID_organizationName, /* 2.5.4.10 */
- OID_organizationUnitName, /* 2.5.4.11 */
- OID_title, /* 2.5.4.12 */
- OID_description, /* 2.5.4.13 */
- OID_name, /* 2.5.4.41 */
- OID_givenName, /* 2.5.4.42 */
- OID_initials, /* 2.5.4.43 */
- OID_generationalQualifier, /* 2.5.4.44 */
- /* Certificate extension IDs */
- OID_subjectKeyIdentifier, /* 2.5.29.14 */
- OID_keyUsage, /* 2.5.29.15 */
- OID_subjectAltName, /* 2.5.29.17 */
- OID_issuerAltName, /* 2.5.29.18 */
- OID_basicConstraints, /* 2.5.29.19 */
- OID_crlDistributionPoints, /* 2.5.29.31 */
- OID_certPolicies, /* 2.5.29.32 */
- OID_authorityKeyIdentifier, /* 2.5.29.35 */
- OID_extKeyUsage, /* 2.5.29.37 */
- /* EC-RDSA */
- OID_gostCPSignA, /* 1.2.643.2.2.35.1 */
- OID_gostCPSignB, /* 1.2.643.2.2.35.2 */
- OID_gostCPSignC, /* 1.2.643.2.2.35.3 */
- OID_gost2012PKey256, /* 1.2.643.7.1.1.1.1 */
- OID_gost2012PKey512, /* 1.2.643.7.1.1.1.2 */
- OID_gost2012Digest256, /* 1.2.643.7.1.1.2.2 */
- OID_gost2012Digest512, /* 1.2.643.7.1.1.2.3 */
- OID_gost2012Signature256, /* 1.2.643.7.1.1.3.2 */
- OID_gost2012Signature512, /* 1.2.643.7.1.1.3.3 */
- OID_gostTC26Sign256A, /* 1.2.643.7.1.2.1.1.1 */
- OID_gostTC26Sign256B, /* 1.2.643.7.1.2.1.1.2 */
- OID_gostTC26Sign256C, /* 1.2.643.7.1.2.1.1.3 */
- OID_gostTC26Sign256D, /* 1.2.643.7.1.2.1.1.4 */
- OID_gostTC26Sign512A, /* 1.2.643.7.1.2.1.2.1 */
- OID_gostTC26Sign512B, /* 1.2.643.7.1.2.1.2.2 */
- OID_gostTC26Sign512C, /* 1.2.643.7.1.2.1.2.3 */
- OID__NR
+};
+extern enum OID look_up_OID(const void *data, size_t datasize); +extern int sprint_oid(const void *, size_t, char *, size_t); +extern int sprint_OID(enum OID, char *, size_t);
+#endif /* _LINUX_OID_REGISTRY_H */ diff --git a/lib/Kconfig b/lib/Kconfig index 26c94f49ecd2..d2955c8feb0e 100644 --- a/lib/Kconfig +++ b/lib/Kconfig @@ -527,6 +527,11 @@ config ASN1 help Enable asn1 decoder library.
+config OID_REGISTRY
- bool
- help
Enable fast lookup object identifier registry.- source lib/efi/Kconfig source lib/efi_loader/Kconfig source lib/optee/Kconfig
diff --git a/lib/Makefile b/lib/Makefile index eb3a675fb8c2..677ec33a1ce1 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -118,4 +118,20 @@ else obj-y += vsprintf.o strto.o strmhz.o endif
+# +# Build a fast OID lookip registry from include/linux/oid_registry.h +# +obj-$(CONFIG_OID_REGISTRY) += oid_registry.o
+$(obj)/oid_registry.o: $(obj)/oid_registry_data.c
+$(obj)/oid_registry_data.c: $(srctree)/include/linux/oid_registry.h \
$(src)/build_OID_registry- $(call cmd,build_OID_registry)
+quiet_cmd_build_OID_registry = GEN $@
cmd_build_OID_registry = perl $(srctree)/$(src)/build_OID_registry $< $@+clean-files += oid_registry_data.c
- subdir-ccflags-$(CONFIG_CC_OPTIMIZE_LIBS_FOR_SPEED) += -O2
diff --git a/lib/build_OID_registry b/lib/build_OID_registry new file mode 100755 index 000000000000..d7fc32ea8ac2 --- /dev/null +++ b/lib/build_OID_registry @@ -0,0 +1,203 @@ +#!/usr/bin/perl -w +# SPDX-License-Identifier: GPL-2.0-or-later +# +# Build a static ASN.1 Object Identified (OID) registry +# +# Copyright (C) 2012 Red Hat, Inc. All Rights Reserved. +# Written by David Howells (dhowells@redhat.com) +#
+use strict;
+my @names = (); +my @oids = ();
+if ($#ARGV != 1) {
- print STDERR "Format: ", $0, " <in-h-file> <out-c-file>\n";
- exit(2);
+}
+# +# Open the file to read from +# +open IN_FILE, "<$ARGV[0]" || die; +while (<IN_FILE>) {
- chomp;
- if (m!\s+OID_([a-zA-z][a-zA-Z0-9_]+),\s+/[*]\s+([012][.0-9]*)\s+[*]/!) {
- push @names, $1;
- push @oids, $2;
- }
+} +close IN_FILE || die;
+# +# Open the files to write into +# +open C_FILE, ">$ARGV[1]" or die; +print C_FILE "/*\n"; +print C_FILE " * Automatically generated by ", $0, ". Do not edit\n"; +print C_FILE " */\n";
+# +# Split the data up into separate lists and also determine the lengths of the +# encoded data arrays. +# +my @indices = (); +my @lengths = (); +my $total_length = 0;
+for (my $i = 0; $i <= $#names; $i++) {
- my $name = $names[$i];
- my $oid = $oids[$i];
- my @components = split(/[.]/, $oid);
- # Determine the encoded length of this OID
- my $size = $#components;
- for (my $loop = 2; $loop <= $#components; $loop++) {
- my $c = $components[$loop];
- # We will base128 encode the number
- my $tmp = ($c == 0) ? 0 : int(log($c)/log(2));
- $tmp = int($tmp / 7);
- $size += $tmp;
- }
- push @lengths, $size;
- push @indices, $total_length;
- $total_length += $size;
+}
+# +# Emit the look-up-by-OID index table +# +print C_FILE "\n"; +if ($total_length <= 255) {
- print C_FILE "static const unsigned char oid_index[OID__NR + 1] = {\n";
+} else {
- print C_FILE "static const unsigned short oid_index[OID__NR + 1] = {\n";
+} +for (my $i = 0; $i <= $#names; $i++) {
- print C_FILE "\t[OID_", $names[$i], "] = ", $indices[$i], ",\n"
+} +print C_FILE "\t[OID__NR] = ", $total_length, "\n"; +print C_FILE "};\n";
+# +# Encode the OIDs +# +my @encoded_oids = ();
+for (my $i = 0; $i <= $#names; $i++) {
- my @octets = ();
- my @components = split(/[.]/, $oids[$i]);
- push @octets, $components[0] * 40 + $components[1];
- for (my $loop = 2; $loop <= $#components; $loop++) {
- my $c = $components[$loop];
- # Base128 encode the number
- my $tmp = ($c == 0) ? 0 : int(log($c)/log(2));
- $tmp = int($tmp / 7);
- for (; $tmp > 0; $tmp--) {
push @octets, (($c >> $tmp * 7) & 0x7f) | 0x80;- }
- push @octets, $c & 0x7f;
- }
- push @encoded_oids, @octets;
+}
+# +# Create a hash value for each OID +# +my @hash_values = (); +for (my $i = 0; $i <= $#names; $i++) {
- my @octets = @{$encoded_oids[$i]};
- my $hash = $#octets;
- foreach (@octets) {
- $hash += $_ * 33;
- }
- $hash = ($hash >> 24) ^ ($hash >> 16) ^ ($hash >> 8) ^ ($hash);
- push @hash_values, $hash & 0xff;
+}
+# +# Emit the OID data +# +print C_FILE "\n"; +print C_FILE "static const unsigned char oid_data[", $total_length, "] = {\n"; +for (my $i = 0; $i <= $#names; $i++) {
- my @octets = @{$encoded_oids[$i]};
- print C_FILE "\t";
- print C_FILE $_, ", " foreach (@octets);
- print C_FILE "\t// ", $names[$i];
- print C_FILE "\n";
+} +print C_FILE "};\n";
+# +# Build the search index table (ordered by length then hash then content) +# +my @index_table = ( 0 .. $#names );
+@index_table = sort {
- my @octets_a = @{$encoded_oids[$a]};
- my @octets_b = @{$encoded_oids[$b]};
- return $hash_values[$a] <=> $hash_values[$b]
- if ($hash_values[$a] != $hash_values[$b]);
- return $#octets_a <=> $#octets_b
- if ($#octets_a != $#octets_b);
- for (my $i = $#octets_a; $i >= 0; $i--) {
- return $octets_a[$i] <=> $octets_b[$i]
if ($octets_a[$i] != $octets_b[$i]);- }
- return 0;
+} @index_table;
+# +# Emit the search index and hash value table +# +print C_FILE "\n"; +print C_FILE "static const struct {\n"; +print C_FILE "\tunsigned char hash;\n"; +if ($#names <= 255) {
- print C_FILE "\tenum OID oid : 8;\n";
+} else {
- print C_FILE "\tenum OID oid : 16;\n";
+} +print C_FILE "} oid_search_table[OID__NR] = {\n"; +for (my $i = 0; $i <= $#names; $i++) {
- my @octets = @{$encoded_oids[$index_table[$i]]};
- printf(C_FILE "\t[%3u] = { %3u, OID_%-35s }, // ",
$i,$hash_values[$index_table[$i]],$names[$index_table[$i]]);- printf C_FILE "%02x", $_ foreach (@octets);
- print C_FILE "\n";
+} +print C_FILE "};\n";
+# +# Emit the OID debugging name table +# +#print C_FILE "\n"; +#print C_FILE "const char *const oid_name_table[OID__NR + 1] = {\n"; +# +#for (my $i = 0; $i <= $#names; $i++) { +# print C_FILE "\t"", $names[$i], "",\n" +#} +#print C_FILE "\t"Unknown-OID"\n"; +#print C_FILE "};\n";
+# +# Polish off +# +close C_FILE or die; diff --git a/lib/oid_registry.c b/lib/oid_registry.c new file mode 100644 index 000000000000..209edc73b99f --- /dev/null +++ b/lib/oid_registry.c @@ -0,0 +1,179 @@ +// SPDX-License-Identifier: GPL-2.0-or-later +/* ASN.1 Object identifier (OID) registry
- Copyright (C) 2012 Red Hat, Inc. All Rights Reserved.
- Written by David Howells (dhowells@redhat.com)
- */
+#ifdef __UBOOT__ +#include <linux/compat.h> +#else +#include <linux/module.h> +#include <linux/export.h> +#endif +#include <linux/oid_registry.h> +#include <linux/kernel.h> +#include <linux/errno.h> +#include <linux/bug.h> +#include "oid_registry_data.c"
+MODULE_DESCRIPTION("OID Registry"); +MODULE_AUTHOR("Red Hat, Inc."); +MODULE_LICENSE("GPL");
+/**
- look_up_OID - Find an OID registration for the specified data
- @data: Binary representation of the OID
- @datasize: Size of the binary representation
- */
+enum OID look_up_OID(const void *data, size_t datasize) +{
- const unsigned char *octets = data;
- enum OID oid;
- unsigned char xhash;
- unsigned i, j, k, hash;
- size_t len;
- /* Hash the OID data */
- hash = datasize - 1;
- for (i = 0; i < datasize; i++)
hash += octets[i] * 33;- hash = (hash >> 24) ^ (hash >> 16) ^ (hash >> 8) ^ hash;
- hash &= 0xff;
- /* Binary search the OID registry. OIDs are stored in ascending order
* of hash value then ascending order of size and then in ascending* order of reverse value.*/- i = 0;
- k = OID__NR;
- while (i < k) {
j = (i + k) / 2;xhash = oid_search_table[j].hash;if (xhash > hash) {k = j;continue;}if (xhash < hash) {i = j + 1;continue;}oid = oid_search_table[j].oid;len = oid_index[oid + 1] - oid_index[oid];if (len > datasize) {k = j;continue;}if (len < datasize) {i = j + 1;continue;}/* Variation is most likely to be at the tail end of the* OID, so do the comparison in reverse.*/while (len > 0) {unsigned char a = oid_data[oid_index[oid] + --len];unsigned char b = octets[len];if (a > b) {k = j;goto next;}if (a < b) {i = j + 1;goto next;}}return oid;- next:
;- }
- return OID__NR;
+} +EXPORT_SYMBOL_GPL(look_up_OID);
+/*
- sprint_OID - Print an Object Identifier into a buffer
- @data: The encoded OID to print
- @datasize: The size of the encoded OID
- @buffer: The buffer to render into
- @bufsize: The size of the buffer
- The OID is rendered into the buffer in "a.b.c.d" format and the number of
- bytes is returned. -EBADMSG is returned if the data could not be intepreted
- and -ENOBUFS if the buffer was too small.
- */
+int sprint_oid(const void *data, size_t datasize, char *buffer, size_t bufsize) +{
- const unsigned char *v = data, *end = v + datasize;
- unsigned long num;
- unsigned char n;
- size_t ret;
- int count;
- if (v >= end)
goto bad;- n = *v++;
- ret = count = snprintf(buffer, bufsize, "%u.%u", n / 40, n % 40);
- if (count >= bufsize)
return -ENOBUFS;- buffer += count;
- bufsize -= count;
- while (v < end) {
num = 0;n = *v++;if (!(n & 0x80)) {num = n;} else {num = n & 0x7f;do {if (v >= end)goto bad;n = *v++;num <<= 7;num |= n & 0x7f;} while (n & 0x80);}ret += count = snprintf(buffer, bufsize, ".%lu", num);if (count >= bufsize)return -ENOBUFS;buffer += count;bufsize -= count;- }
- return ret;
+bad:
- snprintf(buffer, bufsize, "(bad)");
- return -EBADMSG;
+} +EXPORT_SYMBOL_GPL(sprint_oid);
+/**
- sprint_OID - Print an Object Identifier into a buffer
- @oid: The OID to print
- @buffer: The buffer to render into
- @bufsize: The size of the buffer
- The OID is rendered into the buffer in "a.b.c.d" format and the number of
- bytes is returned.
- */
+int sprint_OID(enum OID oid, char *buffer, size_t bufsize) +{
- int ret;
- BUG_ON(oid >= OID__NR);
- ret = sprint_oid(oid_data + oid_index[oid],
oid_index[oid + 1] - oid_index[oid],buffer, bufsize);- BUG_ON(ret == -EBADMSG);
- return ret;
+} +EXPORT_SYMBOL_GPL(sprint_OID);