55 ms·

Reading the NSA’s codebase: LemonGraph review

135 points by ohjeez 8y ago

isaachier 8y ago
To be fair, the way malloc is used is actually the preferred way. If you change the type of the pointer variable, the malloc is still valid.
- Chabs 8y ago
  I'm mildly surprised to see the NSA using malloc instead of calloc, especially for allocating what seems to be a partially initialized struct.
  - foobiekr 8y ago
    Really depends on whether they know that all fields will be written before return or not. This way hey are calling malloc() is very common in professional code bases and a safety measure; I’m surprised the author was surprised.
    - mediocrejoker 8y ago
      The way I read it, the author is surprised that struct node_t is typedef'd to node_t* and not simply node_t I am not used to that style so it seems odd to me, but I suppose if it was common in a codebase one would get used to it.
      - convivialdingo 8y ago
        Most compilers in the 80’s and 90s had pretty restricted grammars based on K&R before C89 and newer standards fixed these sort of things. I’ve seen a bit of code like this from then... Off the top of my head, I’m thinking the Amiga toolkit and Xwindows. Old embedded code may still have some of this going on as well.
        foobiekr 8y ago
        Sometimes limits are good. They lead to people playing it safe. I've spent most of my life dealing with C code dating from 1986 and earlier to present day. Once you get used to the stylistic conventions one of the things that falls out is the simplicity even for huge, old legacy code bases. Often little more than grep or etags is sufficient to competently navigate and follow the flow of this kind of code. Simple things are simple: what callstacks can end up here? etc. The code often has the property that if you printed it you'd still be able to navigate it without issue. Given a random page and a line, getting to somewhere would be possible. In comparison so many modern code bases are just completely incomprehensible without a tool in the form of an IDE (and often still quite challenging with them because even the IDE isn't sure, and so you must resort to runtime analysis). So many "tricks" used which require tools and require the tools to be bug free and robust. The closest I have come to "pick it up and you can read and understand it without assistive technologies" is Go.
  - isaachier 8y ago
    I understand the question, but as @AndyKelley taught me (https://github.com/ziglang/zig/pull/993#commitcomment-28918330 https://github.com/ziglang/zig/pull/993#commitcomment-289183...), it is actually worse to zero a value unnecessarily if you can use Valgrind/sanitizers to check for uninitialized values. Initializing the value as zero will prevent the detection of a bad value.
- pksadiq 8y ago
  > To be fair, the way malloc is used is actually the preferred way. Is it really right? In C, isn't it considered bad to cast malloc result as it masks some mistakes? Also, the code doesn't check for NULL for the malloc result.
  - orbifold 8y ago
    Malloc does not fail under Linux unless you are in very peculiar circumstances.
    - jcranmer 8y ago
      Malloc will still fail for overly large allocation sizes. If you try to malloc(-1), for example.
    - krylon 8y ago
      Not everyone is running Linux. And anyway, it is dirty - like crossing the street without looking for cars because traffic around here is very mellow, or peeing without washing your hands afterwards. (That being said, I once helped somebody to write a program whose task it was to deliberately get the host system to the point where malloc(3) failed. It was not as trivial as one might think.)
  - isaachier 8y ago
    I am not referring to the lack of null check. Just the fact that it uses `malloc(sizeof(*x))` instead of using `malloc(sizeof(Type))`.
    - kevin_thibedeau 8y ago
      The latter creates Heisenbugs if you change the type of x and don't track down every malloc to update the type. It is better to avoid using sizeof(typename) if possible. Now the profligate use of leading underscores. That is an issue.
      - posterboy 8y ago
- drewg123 8y ago
  I agree. I always do it this way for this exact reason. However, I'm surprised the author did not point out that they are calling malloc() without checking for a NULL return value.
  - jimrandomh 8y ago
    Checking the return of malloc() for NULL is not currently considered good practice, because (a) on most platforms malloc is guaranteed not to return NULL, even if the system is out of memory, and (b) on the few platforms where malloc can return NULL, handling that case in practice basically never works.
    - tjoff 8y ago
      Malloc will in some cases return null when the allocation is too large. This might happen long before system is out of memory and it is very much indeed preferred and practical to abort allocations in those cases.
      - anyfoo 8y ago
        Those are rather specific cases, though, aren't they? I'd imagine malloc only returns NULL when virtual address space is exhausted, not physical memory. So if you make an exceedingly large allocation for a very specific, massive thing, then yes, you might want to handle that. But if your allocation was rather small, then you are back to what your parent commentator said and are probably better off aborting.
        drewg123 8y ago
        It depends on whether the system you're using overcommits memory. Some OSes (eg Linux) provide settings to limit virtual memory use to some percentage of physical memory. See http://engineering.pivotal.io/post/virtual_memory_settings_in_linux_-_the_problem_with_overcommit/ http://engineering.pivotal.io/post/virtual_memory_settings_i... The only time you should avoid checking malloc() return values are for special mallocs that really cannot return NULL. One example is FreeBSD's kernel malloc() when called with the M_WAITOK flag.
- EpicEng 8y ago
  Why would that be? You don't cast the result of malloc in C. It's wholly unnecessary, adds clutter to the code, and potentially hides an error if you forgot to include stdlib.h. So why would that be "the preferred way"? I've been writing C for some time and no one who knows C casts the return value of malloc.
  - optymizer 8y ago
    The parent comment was referring to the usage of sizeof(). Also, the fact that they cast the result of malloc makes me think they were using a C++ compiler, which will complain that there's no cast.
    - blattimwind 8y ago
      If you're compiling for C++, you should be using static_cast<> instead.
    - EpicEng 8y ago
      >The parent comment was referring to the usage of sizeof(). Ah ok, makes more sense in re-reading now. I was lazy and went off of a child comment. >Also, the fact that they cast the result of malloc makes me think they were using a C++ compiler, which will complain that there's no cast. Definitely could be that.
- deleted 8y ago
  [deleted]
- Matthias247 8y ago
  Passing sizeof(value) to malloc is really fine. But I consider the typedef of a pointer to a node is to the same identifier as the node itself to be pretty bad. It's confusing for readers and new team members. And can even lead to strange when someone forgets to type "struct".
grogenaut 8y ago
Often you wrap a library api with your own to minimize impact of updating library versions to the rest of the codebase or to provide cross version support, not just to say swap it for Oracle. At a game studio I was at we shimmed all of the PS3 API. No system Apu was allowed to leak past one layer in our codebase. It helped us move to PS4 quicker. Or to windows (with everything nerfed) between the consoles.
- maxxxxx 8y ago
  I like to do that too. Having a thin layer over the actual API makes maintenance much easier and you can test your layer better. But it's hard to implement this in a bigger team. A lot of people don't see the point.
  - laumars 8y ago
    It really depends on the API. For stuff that is likely to change it makes sense to abstract away the API calls. eg either because the API provider likes to break stuff or because you need your code to be agnostic towards that particular library eg for portability reasons. But that isn't always a concern and if you're abstracting away an API just for the sake of it then you'll have to question whether you're adding unnecessary complexity and overhead just for the sake of perceived modularity. Like everything in software development, it's about evaluating the right methodologies for the problems rather than hitting every screw with the same hammer.
    - maxxxxx 8y ago
      'Like everything in software development, it's about evaluating the right methodologies for the problems rather than hitting every screw with the same hammer." Very true.
    - joebergeron 8y ago
      Hitting screws with hammers, eh? Ever drive a nail with a drill?
      - 8y ago
potiuper 8y ago
"As an aside, I’m loving the fact that you can figure out the call graph for methods based on the number of underscores prefixed to the name. No underscore, public method. Single underscore, private method used internally. Two underscores, hidden method, used sparingly. At three underscores, I could tell you what it means, but given that this is NSA’s codebase, I’ll have to kill you afterward."
superbatfish 8y ago
What's with the name?? There is already a well-known and popular library for graph analysis (in C++) named "Lemon Graph Library". It is 10 years old. As far as I can tell, this new library is not related in any way. (Am I mistaken?) Did they not simply google for the words "lemon graph" before they published this code base? Or am I missing something?
- isaachier 8y ago
  My guess of how this evolved: LMDB => LemonDB.
- xtrapolate 8y ago
  Do you seriously think they care about re-using a name for a throw-away non-classified project? People have better things to do with their time.
  - ralston 8y ago
    The idea of the NSA googling `lemon graph` then saying "Welp, looks like someone else already has it. Back to the drawing board", is actually pretty hilarious.
schaefer 8y ago
On the topic of code reading, can anyone endorse any tools specific to reading a code base, rather than development? I've been using vim and cscope forever, but I'm wondering if there's anything new and interesting out there. ...or even screencast recommendations of folks that are particularly proficient at this.
- deleted 8y ago
  [deleted]

135 points by ohjeez 8y ago

To be fair, the way malloc is used is actually the preferred way. If you change the type of the pointer variable, the malloc is still valid.

Chabs 8y ago
I'm mildly surprised to see the NSA using malloc instead of calloc, especially for allocating what seems to be a partially initialized struct.
- foobiekr 8y ago
  Really depends on whether they know that all fields will be written before return or not. This way hey are calling malloc() is very common in professional code bases and a safety measure; I’m surprised the author was surprised.
  - mediocrejoker 8y ago
    The way I read it, the author is surprised that struct node_t is typedef'd to node_t* and not simply node_t I am not used to that style so it seems odd to me, but I suppose if it was common in a codebase one would get used to it.
    - convivialdingo 8y ago
      Most compilers in the 80’s and 90s had pretty restricted grammars based on K&R before C89 and newer standards fixed these sort of things. I’ve seen a bit of code like this from then... Off the top of my head, I’m thinking the Amiga toolkit and Xwindows. Old embedded code may still have some of this going on as well.
      - foobiekr 8y ago
        Sometimes limits are good. They lead to people playing it safe. I've spent most of my life dealing with C code dating from 1986 and earlier to present day. Once you get used to the stylistic conventions one of the things that falls out is the simplicity even for huge, old legacy code bases. Often little more than grep or etags is sufficient to competently navigate and follow the flow of this kind of code. Simple things are simple: what callstacks can end up here? etc. The code often has the property that if you printed it you'd still be able to navigate it without issue. Given a random page and a line, getting to somewhere would be possible. In comparison so many modern code bases are just completely incomprehensible without a tool in the form of an IDE (and often still quite challenging with them because even the IDE isn't sure, and so you must resort to runtime analysis). So many "tricks" used which require tools and require the tools to be bug free and robust. The closest I have come to "pick it up and you can read and understand it without assistive technologies" is Go.
- isaachier 8y ago
  I understand the question, but as @AndyKelley taught me (https://github.com/ziglang/zig/pull/993#commitcomment-28918330 https://github.com/ziglang/zig/pull/993#commitcomment-289183...), it is actually worse to zero a value unnecessarily if you can use Valgrind/sanitizers to check for uninitialized values. Initializing the value as zero will prevent the detection of a bad value.
pksadiq 8y ago
> To be fair, the way malloc is used is actually the preferred way. Is it really right? In C, isn't it considered bad to cast malloc result as it masks some mistakes? Also, the code doesn't check for NULL for the malloc result.
- orbifold 8y ago
  Malloc does not fail under Linux unless you are in very peculiar circumstances.
  - jcranmer 8y ago
    Malloc will still fail for overly large allocation sizes. If you try to malloc(-1), for example.
  - krylon 8y ago
    Not everyone is running Linux. And anyway, it is dirty - like crossing the street without looking for cars because traffic around here is very mellow, or peeing without washing your hands afterwards. (That being said, I once helped somebody to write a program whose task it was to deliberately get the host system to the point where malloc(3) failed. It was not as trivial as one might think.)
- isaachier 8y ago
  I am not referring to the lack of null check. Just the fact that it uses `malloc(sizeof(*x))` instead of using `malloc(sizeof(Type))`.
  - kevin_thibedeau 8y ago
    The latter creates Heisenbugs if you change the type of x and don't track down every malloc to update the type. It is better to avoid using sizeof(typename) if possible. Now the profligate use of leading underscores. That is an issue.
    - posterboy 8y ago
drewg123 8y ago
I agree. I always do it this way for this exact reason. However, I'm surprised the author did not point out that they are calling malloc() without checking for a NULL return value.
- jimrandomh 8y ago
  Checking the return of malloc() for NULL is not currently considered good practice, because (a) on most platforms malloc is guaranteed not to return NULL, even if the system is out of memory, and (b) on the few platforms where malloc can return NULL, handling that case in practice basically never works.
  - tjoff 8y ago
    Malloc will in some cases return null when the allocation is too large. This might happen long before system is out of memory and it is very much indeed preferred and practical to abort allocations in those cases.
    - anyfoo 8y ago
      Those are rather specific cases, though, aren't they? I'd imagine malloc only returns NULL when virtual address space is exhausted, not physical memory. So if you make an exceedingly large allocation for a very specific, massive thing, then yes, you might want to handle that. But if your allocation was rather small, then you are back to what your parent commentator said and are probably better off aborting.
      - drewg123 8y ago
        It depends on whether the system you're using overcommits memory. Some OSes (eg Linux) provide settings to limit virtual memory use to some percentage of physical memory. See http://engineering.pivotal.io/post/virtual_memory_settings_in_linux_-_the_problem_with_overcommit/ http://engineering.pivotal.io/post/virtual_memory_settings_i... The only time you should avoid checking malloc() return values are for special mallocs that really cannot return NULL. One example is FreeBSD's kernel malloc() when called with the M_WAITOK flag.
EpicEng 8y ago
Why would that be? You don't cast the result of malloc in C. It's wholly unnecessary, adds clutter to the code, and potentially hides an error if you forgot to include stdlib.h. So why would that be "the preferred way"? I've been writing C for some time and no one who knows C casts the return value of malloc.
- optymizer 8y ago
  The parent comment was referring to the usage of sizeof(). Also, the fact that they cast the result of malloc makes me think they were using a C++ compiler, which will complain that there's no cast.
  - blattimwind 8y ago
    If you're compiling for C++, you should be using static_cast<> instead.
  - EpicEng 8y ago
    >The parent comment was referring to the usage of sizeof(). Ah ok, makes more sense in re-reading now. I was lazy and went off of a child comment. >Also, the fact that they cast the result of malloc makes me think they were using a C++ compiler, which will complain that there's no cast. Definitely could be that.
deleted 8y ago
[deleted]
Matthias247 8y ago
Passing sizeof(value) to malloc is really fine. But I consider the typedef of a pointer to a node is to the same identifier as the node itself to be pretty bad. It's confusing for readers and new team members. And can even lead to strange when someone forgets to type "struct".

grogenaut 8y ago

Often you wrap a library api with your own to minimize impact of updating library versions to the rest of the codebase or to provide cross version support, not just to say swap it for Oracle. At a game studio I was at we shimmed all of the PS3 API. No system Apu was allowed to leak past one layer in our codebase. It helped us move to PS4 quicker. Or to windows (with everything nerfed) between the consoles.

maxxxxx 8y ago
I like to do that too. Having a thin layer over the actual API makes maintenance much easier and you can test your layer better. But it's hard to implement this in a bigger team. A lot of people don't see the point.
- laumars 8y ago
  It really depends on the API. For stuff that is likely to change it makes sense to abstract away the API calls. eg either because the API provider likes to break stuff or because you need your code to be agnostic towards that particular library eg for portability reasons. But that isn't always a concern and if you're abstracting away an API just for the sake of it then you'll have to question whether you're adding unnecessary complexity and overhead just for the sake of perceived modularity. Like everything in software development, it's about evaluating the right methodologies for the problems rather than hitting every screw with the same hammer.
  - maxxxxx 8y ago
    'Like everything in software development, it's about evaluating the right methodologies for the problems rather than hitting every screw with the same hammer." Very true.
  - joebergeron 8y ago
    Hitting screws with hammers, eh? Ever drive a nail with a drill?
    - 8y ago

potiuper 8y ago

"As an aside, I’m loving the fact that you can figure out the call graph for methods based on the number of underscores prefixed to the name. No underscore, public method. Single underscore, private method used internally. Two underscores, hidden method, used sparingly. At three underscores, I could tell you what it means, but given that this is NSA’s codebase, I’ll have to kill you afterward."

superbatfish 8y ago

What's with the name?? There is already a well-known and popular library for graph analysis (in C++) named "Lemon Graph Library". It is 10 years old. As far as I can tell, this new library is not related in any way. (Am I mistaken?) Did they not simply google for the words "lemon graph" before they published this code base? Or am I missing something?

isaachier 8y ago
My guess of how this evolved: LMDB => LemonDB.
xtrapolate 8y ago
Do you seriously think they care about re-using a name for a throw-away non-classified project? People have better things to do with their time.
- ralston 8y ago
  The idea of the NSA googling `lemon graph` then saying "Welp, looks like someone else already has it. Back to the drawing board", is actually pretty hilarious.

schaefer 8y ago

On the topic of code reading, can anyone endorse any tools specific to reading a code base, rather than development? I've been using vim and cscope forever, but I'm wondering if there's anything new and interesting out there. ...or even screencast recommendations of folks that are particularly proficient at this.

deleted 8y ago
[deleted]