oid_registry: allow arbitrary size OIDs

[PATCH] oid_registry: allow arbitrary size OIDs

Posted by James Bottomley 6 days, 5 hours ago

The current OID registry parser uses 64 bit arithmetic which limits us
to supporting 64 bit or smaller OIDs.  This isn't usually a problem
except that it prevents us from representing the 2.25. prefix OIDs
which are the OID representation of UUIDs and have a 128 bit number
following the prefix.  Rather than import not often used perl
arithmetic modules, replace the current perl 64 bit arithmetic with a
callout to bc, which is arbitrary precision.

Signed-off-by: James Bottomley <James.Bottomley@HansenPartnership.com>
---
 lib/build_OID_registry | 29 +++++++++++++++++++++--------
 1 file changed, 21 insertions(+), 8 deletions(-)

diff --git a/lib/build_OID_registry b/lib/build_OID_registry
index 8267e8d71338..7111537eaff8 100755
--- a/lib/build_OID_registry
+++ b/lib/build_OID_registry
@@ -60,10 +60,12 @@ for (my $i = 0; $i <= $#names; $i++) {
     # Determine the encoded length of this OID
     my $size = $#components;
     for (my $loop = 2; $loop <= $#components; $loop++) {
-	my $c = $components[$loop];
+	$ENV{'BC_LINE_LENGTH'} = "200";
+	my $c = `echo "ibase=10; obase=2; $components[$loop]" | bc`;
+	chomp($c);
 
 	# We will base128 encode the number
-	my $tmp = ($c == 0) ? 0 : int(log($c)/log(2));
+	my $tmp = length($c) - 1;
 	$tmp = int($tmp / 7);
 	$size += $tmp;
     }
@@ -100,16 +102,27 @@ for (my $i = 0; $i <= $#names; $i++) {
     push @octets, $components[0] * 40 + $components[1];
 
     for (my $loop = 2; $loop <= $#components; $loop++) {
-	my $c = $components[$loop];
+	# get the base 2 representation of the component
+	$ENV{'BC_LINE_LENGTH'} = "200";
+	my $c = `echo "ibase=10; obase=2; $components[$loop]" | bc`;
+	chomp($c);
 
-	# Base128 encode the number
-	my $tmp = ($c == 0) ? 0 : int(log($c)/log(2));
+	my $tmp = length($c) - 1;
 	$tmp = int($tmp / 7);
 
-	for (; $tmp > 0; $tmp--) {
-	    push @octets, (($c >> $tmp * 7) & 0x7f) | 0x80;
+	# zero pad upto length multiple of 7
+	$c = substr("0000000", 0, ($tmp + 1) * 7 - length($c)).$c;
+
+	# Base128 encode the number
+	my $j;
+	my $b;
+	for ($j = 0; $j < $tmp; $j++) {
+	    $b = oct("0b".substr($c, $j * 7, 7));
+
+	    push @octets, $b | 0x80;
 	}
-	push @octets, $c & 0x7f;
+	$b = oct("0b".substr($c, $j * 7, 7));
+	push @octets, $b;
     }
 
     push @encoded_oids, \@octets;
-- 
2.51.0

Re: [PATCH] oid_registry: allow arbitrary size OIDs

Posted by David Howells 6 days, 3 hours ago

James Bottomley <James.Bottomley@HansenPartnership.com> wrote:

> This isn't usually a problem
> except that it prevents us from representing the 2.25. prefix OIDs
> which are the OID representation of UUIDs and have a 128 bit number
> following the prefix.

Ewww.

> Rather than import not often used perl arithmetic modules,

Do they not work?  Or are they just not commonly installed?

> +	# Base128 encode the number
> +	my $j;
> +	my $b;
> +	for ($j = 0; $j < $tmp; $j++) {

I would do:

	for (my $j = 0; $j < $tmp; $j++) {

> +	    $b = oct("0b".substr($c, $j * 7, 7));

I would probably do "my $b = ..." here.

> +
> +	    push @octets, $b | 0x80;
>  	}
> -	push @octets, $c & 0x7f;
> +	$b = oct("0b".substr($c, $j * 7, 7));
> +	push @octets, $b;

and just combine these two lines:

	push @octets, oct("0b".substr($c, $j * 7, 7));

Using "oct("0b"...)" looks weird, but I guess it should work.

David

Re: [PATCH] oid_registry: allow arbitrary size OIDs

Posted by James Bottomley 6 days, 1 hour ago

On Tue, 2025-11-25 at 20:33 +0000, David Howells wrote:
> James Bottomley <James.Bottomley@HansenPartnership.com> wrote:
> 
> > This isn't usually a problem
> > except that it prevents us from representing the 2.25. prefix OIDs
> > which are the OID representation of UUIDs and have a 128 bit number
> > following the prefix.
> 
> Ewww.

Yes, well, not responsible for standards bodies ...

> 
> > Rather than import not often used perl arithmetic modules,
> 
> Do they not work?  Or are they just not commonly installed?

 A bit of both: Math::Int128 looked like it might solve my problem but
SUSE doesn't build it.  Math::BigInt is built but has a really horrible
API.  bc is actually an improvement: it's just really converting
decimal to binary at arbitrary size then we just do string operations
on long strings of binary numbers ... it's easier than actual maths ...

> 
> > +	# Base128 encode the number
> > +	my $j;
> > +	my $b;
> > +	for ($j = 0; $j < $tmp; $j++) {
> 
> I would do:
> 
> 	for (my $j = 0; $j < $tmp; $j++) {

OK.

> > +	    $b = oct("0b".substr($c, $j * 7, 7));
> 
> I would probably do "my $b = ..." here.

I can't do that: $b is used outside the scope.

> > +
> > +	    push @octets, $b | 0x80;
> >  	}
> > -	push @octets, $c & 0x7f;
> > +	$b = oct("0b".substr($c, $j * 7, 7));
> > +	push @octets, $b;
> 
> and just combine these two lines:
> 
> 	push @octets, oct("0b".substr($c, $j * 7, 7));

Will do (it was actually that way until I added a debugging printk.

Regards,

James

> 
> Using "oct("0b"...)" looks weird, but I guess it should work.
> 
> David
>

Re: [PATCH] oid_registry: allow arbitrary size OIDs

Posted by Andrew Morton 6 days, 5 hours ago

On Tue, 25 Nov 2025 13:19:56 -0500 James Bottomley <James.Bottomley@HansenPartnership.com> wrote:

> The current OID registry parser uses 64 bit arithmetic which limits us
> to supporting 64 bit or smaller OIDs.  This isn't usually a problem
> except that it prevents us from representing the 2.25. prefix OIDs
> which are the OID representation of UUIDs and have a 128 bit number
> following the prefix.  Rather than import not often used perl
> arithmetic modules, replace the current perl 64 bit arithmetic with a
> callout to bc, which is arbitrary precision.
> 

How big a problem is this in shipped kernels?  Should we backport it?

Re: [PATCH] oid_registry: allow arbitrary size OIDs

Posted by David Howells 6 days, 3 hours ago

Andrew Morton <akpm@linux-foundation.org> wrote:

> How big a problem is this in shipped kernels?  Should we backport it?

Not really much of a problem.  The OIDs that get compiled are all listed in
include/linux/oid_registry.h.  External forces can't add new ones dynamically.

David

Re: [PATCH] oid_registry: allow arbitrary size OIDs

Posted by James Bottomley 6 days, 1 hour ago

On Tue, 2025-11-25 at 20:35 +0000, David Howells wrote:
> Andrew Morton <akpm@linux-foundation.org> wrote:
> 
> > How big a problem is this in shipped kernels?  Should we backport
> > it?
> 
> Not really much of a problem.  The OIDs that get compiled are all
> listed in include/linux/oid_registry.h.  External forces can't add
> new ones dynamically.

Agreed, this only came to light because I was trying to add a 2.25 OID.
What's currently there is all under 32 bit, never mind 64 bit, so no
need to backport.

James

[PATCH v2 1/1] oid_registry: allow arbitrary size OIDs

Posted by James Bottomley 5 days, 4 hours ago

The current OID registry parser uses 64 bit arithmetic which limits us
to supporting 64 bit or smaller OIDs.  This isn't usually a problem
except that it prevents us from representing the 2.25. prefix OIDs
which are the OID representation of UUIDs and have a 128 bit number
following the prefix.  Rather than import not often used perl
arithmetic modules, replace the current perl 64 bit arithmetic with a
callout to bc, which is arbitrary precision, for decimal to base 2
conversion, then do pure string operations on the base 2 number.

Signed-off-by: James Bottomley <James.Bottomley@HansenPartnership.com>

---
v2: tidy up perl with better my placement also set bc to arbitrary size
---
 lib/build_OID_registry | 26 ++++++++++++++++++--------
 1 file changed, 18 insertions(+), 8 deletions(-)

diff --git a/lib/build_OID_registry b/lib/build_OID_registry
index 8267e8d71338..30493ac190c0 100755
--- a/lib/build_OID_registry
+++ b/lib/build_OID_registry
@@ -60,10 +60,12 @@ for (my $i = 0; $i <= $#names; $i++) {
     # Determine the encoded length of this OID
     my $size = $#components;
     for (my $loop = 2; $loop <= $#components; $loop++) {
-	my $c = $components[$loop];
+	$ENV{'BC_LINE_LENGTH'} = "0";
+	my $c = `echo "ibase=10; obase=2; $components[$loop]" | bc`;
+	chomp($c);
 
 	# We will base128 encode the number
-	my $tmp = ($c == 0) ? 0 : int(log($c)/log(2));
+	my $tmp = length($c) - 1;
 	$tmp = int($tmp / 7);
 	$size += $tmp;
     }
@@ -100,16 +102,24 @@ for (my $i = 0; $i <= $#names; $i++) {
     push @octets, $components[0] * 40 + $components[1];
 
     for (my $loop = 2; $loop <= $#components; $loop++) {
-	my $c = $components[$loop];
+	# get the base 2 representation of the component
+	$ENV{'BC_LINE_LENGTH'} = "0";
+	my $c = `echo "ibase=10; obase=2; $components[$loop]" | bc`;
+	chomp($c);
 
-	# Base128 encode the number
-	my $tmp = ($c == 0) ? 0 : int(log($c)/log(2));
+	my $tmp = length($c) - 1;
 	$tmp = int($tmp / 7);
 
-	for (; $tmp > 0; $tmp--) {
-	    push @octets, (($c >> $tmp * 7) & 0x7f) | 0x80;
+	# zero pad upto length multiple of 7
+	$c = substr("0000000", 0, ($tmp + 1) * 7 - length($c)).$c;
+
+	# Base128 encode the number
+	for (my $j = 0; $j < $tmp; $j++) {
+	    my $b = oct("0b".substr($c, $j * 7, 7));
+
+	    push @octets, $b | 0x80;
 	}
-	push @octets, $c & 0x7f;
+	push @octets, oct("0b".substr($c, $tmp * 7, 7));
     }
 
     push @encoded_oids, \@octets;
-- 
2.51.0