3 ms·

So basically, your argument boils down to "well what if the person who implements the dynamic array doesn't know C properly and provides an API that exposes the

So basically, your argument boils down to "well what if the person who implements the dynamic array doesn't know C properly and provides an API that exposes the internal realloc'd memory?". Because if not, I have no idea what kind of insane dynamic array implementation you have in mind. There is no way you should be able to access pointers to the internal memory from the API of a dynamic array. Here's how it works - if your array is of malloc'd structs, then when you access the element, you get back a malloc'd struct. At no point can you access the actual memory, only copies of the values contained at a given index. So yes, I suppose if your bounds checked dynamic array was implemented by a complete novice or someone that doesn't know C, your hypothetical scenario could happen. None of this changes the fact that it's easy for a competent C programmer (do I really need to specify this?) to completely avoid buffer overflows in his own code, which is the only thing I have argued.

kbenson 10y ago
We seem to be talking past each other. I created a bit of sample code ot show exactly what I'm talking about, it's at https://gist.github.com/kbenson/fbc585d6a6144a2a9f1ef340b9135a2e https://gist.github.com/kbenson/fbc585d6a6144a2a9f1ef340b913.... The basic idea is that sometimes you might want a pointer to an array item, if that item is complex, not just a copy of it, as there's no need to be wasteful if it's a fairly large struct. Any pointers to that array might be invalidated if realloc is called on it. Knowing exactly when that happens means you can note that it might be invalid, and do something about it, but if it can happen any time you add items to the array, that means you need to check for whether it was reallocated every time, or assume it's always invalidated whenever you push an item on the array. In the example here, I'm determining the struct with the smallest num field. As I keep allocating space to the array (which I'm doing explicitly here), I'm doing the incorrect thing, which is assuming I can continue to use the pointer, which may no longer be valid and just checking if any of the new items are smaller than the existing smallest. I should be recomputing from scratch. It's obvious when I'm calling realloc, but if I was just pushing new items to the array, it would not be obvious at what point it reallocated to a new location in memory unless I specifically checked. What's happened in that case is we've traded the complexity of explicitly controlling memory allocation of arrays for the complexity of either not allowing pointers to array items or having to keep track of the array location with a separate pointer and checking that they are still the same prior to using any pointers to array items we've stored.
- lacampbell 10y ago
  You're right, to an extent we are talking past each other. I totally understand how your code can cause a dangling pointer. But you are using a raw C array, which completely goes against what I've been poorly trying to explain in this thread. What I am advocating is something like this: https://gist.github.com/anonymous/32df4da4949a6c1067c2be8f203f3ed3 https://gist.github.com/anonymous/32df4da4949a6c1067c2be8f20... so TL;DR, if you don't want to deal with copying structs, malloc them then push them to the dynamic array, and deal with their pointers. Else if you push a struct value on the ray, return struct values.
  - kbenson 10y ago
    > if you don't want to deal with copying structs, malloc them then push them to the dynamic array So, manually manage their memory allocation, but allow dynamic allocation of the array of pointers? Sure, there are some cases where that's useful, but if you're already managing memory for the structs themselves, you can probably just manage the memory for the array at the same time. > Else if you push a struct value on the ray, return struct values. So, like I said, "not allowing pointers to array items". You can do this, but you aren't just making array access a little safer, you're also restricting quite a bit of what you can do for efficiency. If I'm going to throw away the ability to use pointers for efficiency, why am I even using C in the first place? I should just write it in some other language from the start. Presumably I used C because there was a need for that efficiency.
    - lacampbell 10y ago
      So, manually manage their memory allocation, but allow dynamic allocation of the array of pointers? Yes. Sure, there are some cases where that's useful, but if you're already managing memory for the structs themselves, you can probably just manage the memory for the array at the same time. ... then you have memory bugs. As your example code clearly shows. What you're suggesting (exposing the internal backing array of a dynamic array) is completely unorthodox and fraught with potential bugs, and I doubt if rust even does this internally. All I can suggest is that you look up how dynamic arrays are typically implemented in C. The technique I describe is almost universally followed. This is also what happens with std::vector in C++ - std::vector doesn't manage the memory of the elements themselves, just its internal backing array.

kbenson 10y ago

We seem to be talking past each other. I created a bit of sample code ot show exactly what I'm talking about, it's at https://gist.github.com/kbenson/fbc585d6a6144a2a9f1ef340b9135a2e https://gist.github.com/kbenson/fbc585d6a6144a2a9f1ef340b913.... The basic idea is that sometimes you might want a pointer to an array item, if that item is complex, not just a copy of it, as there's no need to be wasteful if it's a fairly large struct. Any pointers to that array might be invalidated if realloc is called on it. Knowing exactly when that happens means you can note that it might be invalid, and do something about it, but if it can happen any time you add items to the array, that means you need to check for whether it was reallocated every time, or assume it's always invalidated whenever you push an item on the array. In the example here, I'm determining the struct with the smallest num field. As I keep allocating space to the array (which I'm doing explicitly here), I'm doing the incorrect thing, which is assuming I can continue to use the pointer, which may no longer be valid and just checking if any of the new items are smaller than the existing smallest. I should be recomputing from scratch. It's obvious when I'm calling realloc, but if I was just pushing new items to the array, it would not be obvious at what point it reallocated to a new location in memory unless I specifically checked. What's happened in that case is we've traded the complexity of explicitly controlling memory allocation of arrays for the complexity of either not allowing pointers to array items or having to keep track of the array location with a separate pointer and checking that they are still the same prior to using any pointers to array items we've stored.

lacampbell 10y ago
You're right, to an extent we are talking past each other. I totally understand how your code can cause a dangling pointer. But you are using a raw C array, which completely goes against what I've been poorly trying to explain in this thread. What I am advocating is something like this: https://gist.github.com/anonymous/32df4da4949a6c1067c2be8f203f3ed3 https://gist.github.com/anonymous/32df4da4949a6c1067c2be8f20... so TL;DR, if you don't want to deal with copying structs, malloc them then push them to the dynamic array, and deal with their pointers. Else if you push a struct value on the ray, return struct values.
- kbenson 10y ago
  > if you don't want to deal with copying structs, malloc them then push them to the dynamic array So, manually manage their memory allocation, but allow dynamic allocation of the array of pointers? Sure, there are some cases where that's useful, but if you're already managing memory for the structs themselves, you can probably just manage the memory for the array at the same time. > Else if you push a struct value on the ray, return struct values. So, like I said, "not allowing pointers to array items". You can do this, but you aren't just making array access a little safer, you're also restricting quite a bit of what you can do for efficiency. If I'm going to throw away the ability to use pointers for efficiency, why am I even using C in the first place? I should just write it in some other language from the start. Presumably I used C because there was a need for that efficiency.
  - lacampbell 10y ago
    So, manually manage their memory allocation, but allow dynamic allocation of the array of pointers? Yes. Sure, there are some cases where that's useful, but if you're already managing memory for the structs themselves, you can probably just manage the memory for the array at the same time. ... then you have memory bugs. As your example code clearly shows. What you're suggesting (exposing the internal backing array of a dynamic array) is completely unorthodox and fraught with potential bugs, and I doubt if rust even does this internally. All I can suggest is that you look up how dynamic arrays are typically implemented in C. The technique I describe is almost universally followed. This is also what happens with std::vector in C++ - std::vector doesn't manage the memory of the elements themselves, just its internal backing array.