550991 - Remove failure checks of infallible allocations

Status: RESOLVED INCOMPLETE

(Developer Infrastructure :: Source Code Analysis, enhancement)

Description

[Chris Jones [:cjones] inactive; ni?/f?/r? if you need me]

This work can proceed in parallel with bug 507249.

Basically, we want to convert this pattern

  Foo* f;
  if (NULL == [infallibly allocate f])
    ...;

into

  Foo* f;
  [infallibly allocate f];

The infallible allocators are

  ::operator new
  ::operator new[]
  moz_xmalloc
  moz_xcalloc
  moz_x* et al.

This problem likely will want an automated tool.  One approach is a pork-only analysis and rewrite program.  Another is doing the analysis with a treehydra script, and have that spit out info that a pork rewrite program reads to decide where to nuke NULL checks.

Comment 1

[(dormant account)]

Ehren might have a script that detects these from bug 517370.

Comment 2

[Ehren Metcalfe]

Attachment: report

I wrote a few treehydra scripts to check for these cases (the stuff I have from bug 517370 isn't precise enough). I think the best method is to scan the ast via process_cp_pre_genericize in order to check for exact patterns. 

I'm going to have to spam the attachment list here but this is what I've found so far:

The number of instances of this pattern:

  Foo* f;
  if (NULL == [infallibly allocate f])
    ...;

is actually pretty low. Counting the number of times an infallible allocator is called within the test expression of an if statement I only ended up with 22 instances. Counting the number of times where that exact pattern or something similar occurs eg
  Foo* f
  if (![infallibly allocate f])
I only ended up with 4 instances.

Looking over the data I think the easiest case would be something like:  
  [infallibly allocate f]
  if (!f)
    /* error handling */

One of my scripts will detect this case or anything similar eg |if (NULL == f)|
and print out the exact start location of the if statement. This could be passed to a pork tool that receives a start loc and just replaces all text until the end loc with "".

Only thing is I only end with 1260 instances of this pattern not counting duplicates (from macros, include files, etc)... may be easier to do it manually. I suppose I should check for the opposite too ie 

if (p is not null) { 
  // do stuff
}

Another easy rewrite would be looking for |NS_ENSURE_TRUE(p, NS_ERROR_OUT_OF_MEMORY);| I don't have anything that looks for these specifically but my main script detects them along with the other checks (the exact identification/removal would be a straightforward sed job).

I came across a weird issue though. When searching more generally for any instances where an infallibly allocated variable is checked, my script kept flagging certain calls to |delete| and |operator delete []|. 

It turns out every call to |delete []| (and |__deleting_dtor|) gets wrapped in an implicit conditional expression, checking if the allocated variable is not null. I guess this is part of the C++ standard but the implementation is suprising:

code like this:

void foo() {
  char* x = new char [16];
  delete [] x;
}

ends up with an ast like this:

;; Function void foo() (_Z3foov)
;; enabled by -tree-original
  char * x;

    char * x;
  <<cleanup_point <<< Unknown tree: expr_stmt
  (void) (x = (char *) operator new [] (16)) >>>
>>;
  <<cleanup_point <<< Unknown tree: expr_stmt
  (if (x != 0B)
    {
      operator delete [] ((void *) x);
    }
  else
    {
      0
    }) >>>
>>;

while code like this: 

void foo() {
  char* x = new char;
  delete x;
}

ends up as this:

;; Function void foo() (_Z3foov)
;; enabled by -tree-original
{
  char * x;

    char * x;
  <<cleanup_point <<< Unknown tree: expr_stmt
  (void) (x = (char *) operator new (1)) >>>
>>;
  <<cleanup_point <<< Unknown tree: expr_stmt
  operator delete (x) >>>
>>;
}

This affects the generated code too, with the first example looking like this:

_Z3foov:
.LFB2:
  pushl %ebp
.LCFI0:
  movl  %esp, %ebp
.LCFI1:
  subl  $24, %esp
.LCFI2:
  movl  $16, (%esp)
  call  _Znaj          # operator new []
  movl  %eax, -4(%ebp)
  cmpl  $0, -4(%ebp)   # is x zero?
  je  .L3              # jump to L3 if so
  movl  -4(%ebp), %eax
  movl  %eax, (%esp)
  call  _ZdaPv # operator delete []
.L3:
  leave
  ret

The second example looks like this (no null check):

_Z3foov:
.LFB2:
  pushl %ebp
.LCFI0:
  movl  %esp, %ebp
.LCFI1:
  subl  $24, %esp
.LCFI2:
  movl  $1, (%esp)
  call  _Znwj          # operator new
  movl  %eax, -4(%ebp)
  movl  -4(%ebp), %eax
  movl  %eax, (%esp)
  call  _ZdlPv         # operator delete
  leave
  ret

I even tried passing NULL to operator delete [] and then manually removing the null check in assembly to see if I could induce a segfault (no luck). The script distinguishes any check of an infallibly allocated var made by an autogenerated, delete wrapping COND_EXPR though (There are only 329 of these not counting duplicates).

(I also notice that there are currently no calls to moz_x* functions at least with my several week old revision)

cjones, do you think I should try using pork here especially with the 1260 if-failure checks? It wouldn't take me too long to manually delete those if this would be valuable.

Comment 3

[Ehren Metcalfe]

Attachment: main script for finding all infallible checks

Comment 4

[Ehren Metcalfe]

Attachment: script for finding |if (p is null)|

Comment 5

[Chris Jones [:cjones] inactive; ni?/f?/r? if you need me]

Nice work!

(In reply to comment #2)
> Only thing is I only end with 1260 instances of this pattern not counting
> duplicates (from macros, include files, etc)... may be easier to do it
> manually.

Very interesting.  This might confirm suspicions that we don't indeed handle OOM to any worthwhile degree.  Could you modify your script to also count allocations that *aren't* NULL checked?  This might be interesting data.

> I suppose I should check for the opposite too ie 
> 
> if (p is not null) { 
>   // do stuff
> }
>

Yes, this would be useful.
 
> It turns out every call to |delete []| (and |__deleting_dtor|) gets wrapped in
> an implicit conditional expression, checking if the allocated variable is not
> null.

Also interesting ;).  According to the spec, both |::operator delete() throw(bad_alloc)| and |::operator delete[]() throw(bad_alloc)| don't need to null check, whereas the nothrow variants do.  Appears to be a gcc bug.  (Our infallible operator news are |throw()|, but since this doesn't seem to affect generated code it's probably not worth fixing yet.)

> I even tried passing NULL to operator delete [] and then manually removing the
> null check in assembly to see if I could induce a segfault (no luck).

In practice these will always call into free(), which makes an additional null check.

> (I also notice that there are currently no calls to moz_x* functions at least
> with my several week old revision)
> 

There's one now ;).

> cjones, do you think I should try using pork here especially with the 1260
> if-failure checks? It wouldn't take me too long to manually delete those if
> this would be valuable.

Whichever you think is most expedient.

Comment 6

[Igor Bukanov]

(In reply to comment #5)
> Very interesting.  This might confirm suspicions that we don't indeed handle
> OOM to any worthwhile degree.

This is very true. For unrelated work I have disabled overcommiting memory on Linux (via  echo 2 > /proc/sys/vm/overcommit_memory) on a system with 2GB of physical memory and no swap. The end result was random crashes and occasional hangs which I am trying to investigate.

Comment 7

[Shriram (irc: Mavericks)]

It's been a while since last Apr'10. I'm interested to know of any updates.

Comment 8

[Chris Jones [:cjones] inactive; ni?/f?/r? if you need me]

No updates.  If you would like to tackle this bug, please do!

Comment 10

[Nicholas Nethercote [inactive]]

Current infallible allocation operations:

- Default `operator new`
- moz_xmalloc, moz_xcalloc, moz_xrealloc, moz_xmemalign, moz_xstrdup, moz_xstrndup, moz_xmemdup
- NS_xstrdup, NS_xstrndup

Comment 11

[Mike Hommey [:glandium]]

A generic way to handle this would be to annotate the declarations of those infallible allocation functions. It's worth noting the attached patch is presumably using dehydra, which we've killed. We use a clang plugin for static analysis, nowadays.

Comment 12

[Andrew McCreight [:mccr8]]

It would be nice to remove these automatically, but that ship has already sailed. If somebody wants to take up a new effort with some kind of rewriting framework, they can file a new bug.