clamp allocations of size 0 to 1 or pass size to free

[thestinger]

A call to malloc(0) may return a null pointer or it may return a unique pointer to an allocation. Rust cannot call malloc(0) as then the check for null to determine if the allocation has failed will not work. I special-cased it to always return null for zero-size allocations to avoid this error case.

However, this has exposed a new issue. If the exchange allocator returns a null pointer, then the assumption of unique pointers being non-null does not hold. For example, Some(~()) is considered to be None.

The only solution I can think of is clamping allocations to a minimum size of 1.

[eddyb]

We could consider ~ZeroSizedType to be zero-sized itself, but that means breaking reference equality (and the invariant that all non-trait-object pointers are... pointer-sized).

[thestinger]

Okay, I came up with a better solution. With optimizations, the address of zero-size types is already irrelevant:

12:08:23  strcat | rusti: let x = (); let y = (); (&x as *(), &y as *())
12:08:25      -- | Notice(rusti) -> #rust-internals: ((0x7fc8bb6bedc8 as *()), (0x7fc8bb6bedc8 as *()))

This is not a problem, because LLVM's NoAlias concept only means that there is no memory dependency between two pointers (there will never be a write through one seen through the other).

Therefore, we can simply return a pointer with the address 1 instead of 0, so it doesn't break the non-null guarantee! However, this is going to involve changing the drop glue for zero-size types to omit the call to free.

[cgaebel]

I will begin a patch for this tomorrow.

[thestinger]

@wowus: We do need to decide on the best way to do this though. Passing the size to free and realloc will preserve the ability to avoid allocation for the zero-size case. I'm thinking we could do this:

static EMPTY: () = ();
static EMPTY_PTR: *mut u8 = &EMPTY as *() as *mut u8;

fn alloc(size: uint) -> *mut u8 {
    if size == 0 {
        EMPTY_PTR
    } else {
        ...
    }
}

fn free(ptr: *mut u8, size: uint) {
    if size != 0 {
        libc::free(ptr);
    }
}

The realloc function would also need to take the old size as a parameter. This will require altering the exchange_malloc lang item to take a length and removing the glue collapsing for ~T where T is Pod. An allocator can take advantage of the size passed to free to find the right pool without as much work.

Alternatively, free could compare against EMPTY_PTR but this will not optimize out as the size check will in the general case. The free wrapper needs to be inlined for dead store elimination to work so it's not a one time cost.

[cgaebel]

@thestinger: what else needs to be done to get this issue closed? Did you effectively fix it with your PR?

[thestinger]

@wowus: The exchange_free lang item is now never called on zero-size allocations. However, a library fix is still necessary. The exchange_malloc function could now return a static pointer.

I don't know if this should also be fixed for malloc_raw and realloc_raw.

[pnkfelix]

cc me

[nikomatsakis]

I don't consider these to be the only two solutions. I think we can also guarantee that any allocation which has zero-size will never be dereferenced or freed and just some non-zero value. This will require that when converting Vec<T> to ~[T], we check for length zero and eagerly free the array (and similarly if we chose to support pop() on ~[T]).

[thestinger]

@nikomatsakis: I did that as part of 1778b63 and #13267.

[nikomatsakis]

@thestinger Indeed. I commented a bit eagerly, I suppose. I read the whole thread now and have some questions:

1. The only case where we do not know statically whether to call free is with [] and Trait, correct?
2. When calling realloc, you say that the size parameter will be optimized away in the common case, but that is not clear to me. We call realloc to grow vectors, and we will (typically) not generally know whether the vector has zero length or not, right? Well, I suppose there is the case of ~[()] to consider. I guess overall my point is that I'm not sure that fixing this within realloc and free etc is the right place, vs the caller.

OTOH, if we can add size checks to free and "fix it once", that is preferable. In any case, I expect we will continue to supply exact sizes to malloc/free (you've convinced me that this makes sense), though I think not all allocators will necessarily care.

[nikomatsakis]

And again I'm late, I suppose, since it seems like the idea of not calling free from the caller is roughly what you did in 898669c.