9 ms·

Can we not have one integer type in c that can grow like in js as required and become bigint if too big?

vbezhenar 5y ago
We can. But it would be very inefficient. There's no point to use C at all, if you can accept that level of performance.
wyager 5y ago
No, because that would require implicit dynamic allocation, which would defeat the entire point of using C.
- airocker 5y ago
  Only when limits are getting breached, otherwise it is one if statement extra on every access. This happens in Java and other languages.
  - wyager 5y ago
    It doesn’t matter if it only happens occasionally. It’s completely inappropriate for C, which has no implicit memory allocation. There’s not even a clear way to include implicit allocation in the semantics of C.
gruez 5y ago
>that can grow like in js I thought js "integers" are just floating point numbers?
- OnlyLys 5y ago
  I believe the poster you were replying to was talking about JS's new `BigInt` type. https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/BigInt https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...
  - vbezhenar 5y ago
    Good example of that feature is Python. Also, AFAIR, Scheme (and probably some other lisps) support it.
wyldfire 5y ago
Yes, arbitrary precision integers could theoretically become a C language/library feature. But let's say that it gets proposed and accepted and it's integrated into popular compiler toolchains. The kernel wouldn't leverage it here or likely anywhere else because of its cost. A newly designed OS kernel could perhaps take on this kind of feature. This would be the kind of OS that could be formally verified and would be willing to pay that runtime cost for arbitrary precision.
- airocker 5y ago
  Perhaps such type of things have been put in Kernel before.
- kaba0 5y ago
  C doesn’t have the abstraction power to make anything with such a datatype.
  - wyldfire 5y ago
    I left myself a lot of latitude when I referred to this as a potential "language/library feature". typedef struct { /* TODO */ } arb_int; arb_int *new_arb_int(void); void delete_arb_int(arb_int *); arb_int *arb_int_add(arb_int *, arb_int *); arb_int *arb_int_sub(arb_int *, arb_int *); arb_int *arb_int_mul(arb_int *, arb_int *); arb_int *arb_int_div(arb_int *, arb_int *); bool arb_int_gt(arb_int *, arb_int *); bool arb_int_lt(arb_int *, arb_int *); bool arb_int_gte(arb_int *, arb_int *); bool arb_int_lte(arb_int *, arb_int *); bool arb_int_eq(arb_int *, arb_int *);
dbrgn 5y ago
Haha, yeah JS integers "can grow". Kind of. And then they bite you in the worst way possible. Especially when combined with cryptography (e.g. nonces). Try this: >> const x = 288230376151711740; >> x == x + 1 true Or this: >> 2\*1024 Infinity JS doesn't even have integers. It only has floats. JS is by far the worst language I know of when it comes to integer support. If you want a better example of arbitrary precision integers, try Python, for example.
- _moof 5y ago
  I was working at Twitter when we learned this the hard way. We switched to a separate service for generating tweet IDs (instead of MySQL sequences), which for various distributed systems reasons meant IDs started taking up more bits. And when we stuck those bigger IDs into JSON responses in the API... well, we learned the dumbest lesson possible about the intersection between JSON, JavaScript, and double-precision floating-point. Later that day the "id_str" fields were born.
  - dbrgn 5y ago
    Yep, I can totally relate. I found multiple bugs in a MessagePack JS implementation that were related to this issue. I also worked on a project once where unique IDs of objects could get quite large (because they were random u64 integers). Those IDs were serialized and sent to a browser. Sometimes two objects were viewed as "the same" in the browser application because their IDs were truncated by the floating point precision issue.
- johndough 5y ago
  Neat trick. Math.pow(2, 53) == Math.pow(2, 53) + 1 This is a bit clearer I think. The addition just barely overflows the 53 mantissa bits of the IEEE 754 double precision floating point number. By the way, JS has BigInts these days, which are supported by all major browsers: https://caniuse.com/bigint https://caniuse.com/bigint >> const x = 288230376151711740n; >> x == x + 1n false
  - mirekrusin 5y ago
infamouscow 5y ago
We can do this in software because there's virtually no limit to the abstractions people make, but hardware doesn't work like that. At some point in the software stack we need to draw a line and say this is a 64-bit signed integer that hardware can understand.
- airocker 5y ago
  But should it be everywhere including the fs/virtual fs layer? Could we limit it only to device drivers? Not a kernel expert here and would love to hear thoughts.
  - dahfizz 5y ago
    This doesn't have anything to do with filesystems or kernels. The x86 assembly uses fixed width immediates. CPU registers are a fixed width. For any code to compile and run, it needs to make decisions about how large stack frames need to be, and how much heap memory to allocate. This was the parent's point about abstractions. You can make a library that pretends to be a variable sized integer, but to implement such a library you need to make a decision about how much space to allocate and the width of variables in order to compile. There is no getting away from how the hardware works.
    - airocker 5y ago
      Yes totally, but FS is a Kernel abstraction, it deals with questions like: How to keep a directory? How to keep a file? How to keep synlinks. Etc, These can be implemented in any higher level language or within C without using fixed width numerals if correct abstractions were available. Only device control parts should use fixed with numerals in my opinion.
      - infamouscow 5y ago
        The problem is syscall interfaces are facilitated through hardware circuits, and as such, you have to work with fixed-width integers. Not only that, but those integers usually have other requirements around alignment and endianness.
jerf 5y ago
We don't need arbitrary-sized integers; we need exceptions on overflow (or underflow, but I'll stick to overflow for the rest of this post) to be the default, or similar language features as appropriate. I for one am tired of the chicken & egg issue of "CPUs don't support efficient overflow checking because nobody uses it, so it's slow" and "Overflow checking is slow because the CPU doesn't support it, so nobody uses it". For all the other good security work done in both software and hardware, much for things far more complex than this, this seems like an absolutely batshit insane oversight considering the cost/benefits for fixing this.
- airocker 5y ago
  CPU would raise a signal just as null pointer exception? And it seems a lot of code (for eg, safeintadd metioned below) assumes no exception. Would not all that code get messed up? Would it be possible to just silently replace with arbitrary sized integer and not break any code like safeintadd?
  - dahfizz 5y ago
    CPUs don't raise exceptions, that is a software concept. CPUs do have traps, like for division by zero, but those are not exceptions in the way you think. Null pointers are also handled by the kernel, not the CPU. Its called a segmentation fault because you are trying to access a memory segment that the OS doesn't want you to.
    - airocker 5y ago
      I dont think kernel handles NPEs: https://stackoverflow.com/questions/63091446/what-happens-at-cpu-level-if-you-dereference-a-null-pointer https://stackoverflow.com/questions/63091446/what-happens-at...
      - account42 5y ago
        From your link: A NULL pointer in most (but not all) C implementations is address 0. Normally this address is not in a valid (mapped) page. Any access to a virtual page that's not mapped by the HW page tables results in a page-fault exception. e.g. on x86, #PF. This invokes the OS's page-fault exception handler to resolve the situation.

We can. But it would be very inefficient. There's no point to use C at all, if you can accept that level of performance.

wyager 5y ago

No, because that would require implicit dynamic allocation, which would defeat the entire point of using C.

airocker 5y ago
Only when limits are getting breached, otherwise it is one if statement extra on every access. This happens in Java and other languages.
- wyager 5y ago
  It doesn’t matter if it only happens occasionally. It’s completely inappropriate for C, which has no implicit memory allocation. There’s not even a clear way to include implicit allocation in the semantics of C.

gruez 5y ago

>that can grow like in js I thought js "integers" are just floating point numbers?

OnlyLys 5y ago
I believe the poster you were replying to was talking about JS's new `BigInt` type. https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/BigInt https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...
- vbezhenar 5y ago
  Good example of that feature is Python. Also, AFAIR, Scheme (and probably some other lisps) support it.

wyldfire 5y ago

Yes, arbitrary precision integers could theoretically become a C language/library feature. But let's say that it gets proposed and accepted and it's integrated into popular compiler toolchains. The kernel wouldn't leverage it here or likely anywhere else because of its cost. A newly designed OS kernel could perhaps take on this kind of feature. This would be the kind of OS that could be formally verified and would be willing to pay that runtime cost for arbitrary precision.

airocker 5y ago
Perhaps such type of things have been put in Kernel before.
kaba0 5y ago
C doesn’t have the abstraction power to make anything with such a datatype.
- wyldfire 5y ago
  I left myself a lot of latitude when I referred to this as a potential "language/library feature". typedef struct { /* TODO */ } arb_int; arb_int *new_arb_int(void); void delete_arb_int(arb_int *); arb_int *arb_int_add(arb_int *, arb_int *); arb_int *arb_int_sub(arb_int *, arb_int *); arb_int *arb_int_mul(arb_int *, arb_int *); arb_int *arb_int_div(arb_int *, arb_int *); bool arb_int_gt(arb_int *, arb_int *); bool arb_int_lt(arb_int *, arb_int *); bool arb_int_gte(arb_int *, arb_int *); bool arb_int_lte(arb_int *, arb_int *); bool arb_int_eq(arb_int *, arb_int *);

dbrgn 5y ago

Haha, yeah JS integers "can grow". Kind of. And then they bite you in the worst way possible. Especially when combined with cryptography (e.g. nonces). Try this: >> const x = 288230376151711740; >> x == x + 1 true Or this: >> 2\*1024 Infinity JS doesn't even have integers. It only has floats. JS is by far the worst language I know of when it comes to integer support. If you want a better example of arbitrary precision integers, try Python, for example.

_moof 5y ago
I was working at Twitter when we learned this the hard way. We switched to a separate service for generating tweet IDs (instead of MySQL sequences), which for various distributed systems reasons meant IDs started taking up more bits. And when we stuck those bigger IDs into JSON responses in the API... well, we learned the dumbest lesson possible about the intersection between JSON, JavaScript, and double-precision floating-point. Later that day the "id_str" fields were born.
- dbrgn 5y ago
  Yep, I can totally relate. I found multiple bugs in a MessagePack JS implementation that were related to this issue. I also worked on a project once where unique IDs of objects could get quite large (because they were random u64 integers). Those IDs were serialized and sent to a browser. Sometimes two objects were viewed as "the same" in the browser application because their IDs were truncated by the floating point precision issue.
johndough 5y ago
Neat trick. Math.pow(2, 53) == Math.pow(2, 53) + 1 This is a bit clearer I think. The addition just barely overflows the 53 mantissa bits of the IEEE 754 double precision floating point number. By the way, JS has BigInts these days, which are supported by all major browsers: https://caniuse.com/bigint https://caniuse.com/bigint >> const x = 288230376151711740n; >> x == x + 1n false
- mirekrusin 5y ago

infamouscow 5y ago

We can do this in software because there's virtually no limit to the abstractions people make, but hardware doesn't work like that. At some point in the software stack we need to draw a line and say this is a 64-bit signed integer that hardware can understand.

airocker 5y ago
But should it be everywhere including the fs/virtual fs layer? Could we limit it only to device drivers? Not a kernel expert here and would love to hear thoughts.
- dahfizz 5y ago
  This doesn't have anything to do with filesystems or kernels. The x86 assembly uses fixed width immediates. CPU registers are a fixed width. For any code to compile and run, it needs to make decisions about how large stack frames need to be, and how much heap memory to allocate. This was the parent's point about abstractions. You can make a library that pretends to be a variable sized integer, but to implement such a library you need to make a decision about how much space to allocate and the width of variables in order to compile. There is no getting away from how the hardware works.
  - airocker 5y ago
    Yes totally, but FS is a Kernel abstraction, it deals with questions like: How to keep a directory? How to keep a file? How to keep synlinks. Etc, These can be implemented in any higher level language or within C without using fixed width numerals if correct abstractions were available. Only device control parts should use fixed with numerals in my opinion.
    - infamouscow 5y ago
      The problem is syscall interfaces are facilitated through hardware circuits, and as such, you have to work with fixed-width integers. Not only that, but those integers usually have other requirements around alignment and endianness.

jerf 5y ago

We don't need arbitrary-sized integers; we need exceptions on overflow (or underflow, but I'll stick to overflow for the rest of this post) to be the default, or similar language features as appropriate. I for one am tired of the chicken & egg issue of "CPUs don't support efficient overflow checking because nobody uses it, so it's slow" and "Overflow checking is slow because the CPU doesn't support it, so nobody uses it". For all the other good security work done in both software and hardware, much for things far more complex than this, this seems like an absolutely batshit insane oversight considering the cost/benefits for fixing this.

airocker 5y ago
CPU would raise a signal just as null pointer exception? And it seems a lot of code (for eg, safeintadd metioned below) assumes no exception. Would not all that code get messed up? Would it be possible to just silently replace with arbitrary sized integer and not break any code like safeintadd?
- dahfizz 5y ago
  CPUs don't raise exceptions, that is a software concept. CPUs do have traps, like for division by zero, but those are not exceptions in the way you think. Null pointers are also handled by the kernel, not the CPU. Its called a segmentation fault because you are trying to access a memory segment that the OS doesn't want you to.
  - airocker 5y ago
    I dont think kernel handles NPEs: https://stackoverflow.com/questions/63091446/what-happens-at-cpu-level-if-you-dereference-a-null-pointer https://stackoverflow.com/questions/63091446/what-happens-at...
    - account42 5y ago
      From your link: A NULL pointer in most (but not all) C implementations is address 0. Normally this address is not in a valid (mapped) page. Any access to a virtual page that's not mapped by the HW page tables results in a page-fault exception. e.g. on x86, #PF. This invokes the OS's page-fault exception handler to resolve the situation.