> On Oct 27, 2023, at 10:53 AM, Martin Uecker <uec...@tugraz.at> wrote:
>
> Am Freitag, dem 27.10.2023 um 14:32 +0000 schrieb Qing Zhao:
>>
>>> On Oct 27, 2023, at 3:21 AM, Martin Uecker <uec...@tugraz.at> wrote:
>>>
>>> Am Donnerstag, dem 26.10.2023 um 19:57 +0000 schrieb Qing Zhao:
>>>> I guess that what Kees wanted, ""fill the array without knowing the actual
>>>> final size" code pattern”, as following:
>>>>
>>>>>> struct foo *f;
>>>>>> char *p;
>>>>>> int i;
>>>>>>
>>>>>> f = alloc(maximum_possible);
>>>>>> f->count = 0;
>>>>>> p = f->buf;
>>>>>>
>>>>>> for (i; data_is_available() && i < maximum_possible; i++) {
>>>>>> f->count ++;
>>>>>> p[i] = next_data_item();
>>>>>> }
>>>>
>>>> actually is a dynamic array, or more accurately, Bounded-size dynamic
>>>> array: ( but not a dynamic allocated array as we discussed so far)
>>>>
>>>> https://en.wikipedia.org/wiki/Dynamic_array
>>>>
>>>> This dynamic array, also is called growable array, or resizable array,
>>>> whose size can
>>>> be changed during the lifetime.
>>>>
>>>> For VLA or FAM, I believe that they are both dynamic allocated array, i.e,
>>>> even though the size is not know at the compilation time, but the size
>>>> will be fixed after the array is allocated.
>>>>
>>>> I am not sure whether C has support to such Dynamic array? Or whether it’s
>>>> easy to provide dynamic array support in C?
>>>
>>> It is possible to support dynamic arrays in C even with
>>> good checking, but not safely using the pattern above
>>> where you derive a pointer which you later use independently.
>>>
>>> While we could track the connection to the original struct,
>>> the necessary synchronization between the counter and the
>>> access to the buffer is difficult. I do not see how this
>>> could be supported with reasonable effort and cost.
>>>
>>>
>>> But with this restriction in mind, we can do a lot in C.
>>> For example, see my experimental (!) container library
>>> which has vector type.
>>> https://github.com/uecker/noplate/blob/main/test.c
>>> You can get an array view for the vector (which then
>>> also can decay to a pointer), so it interoperates nicely
>>> with C but you can get good bounds checking.
>>>
>>>
>>> But once you derive a pointer and pass it on, it gets
>>> difficult. But if you want safety, you just have to
>>> to simply avoid this in code.
>>
>> So, for the following modified code: (without the additional pointer “p”)
>>
>> struct foo
>> {
>> size_t count;
>> char buf[] __attribute__((counted_by(count)));
>> };
>>
>> struct foo *f;
>> int i;
>>
>> f = alloc(maximum_possible);
>> f->count = 0;
>>
>> for (i; data_is_available() && i < maximum_possible; i++) {
>> f->count ++;
>> f->buf[i] = next_data_item();
>> }
>>
>> The support for dynamic array should be possible?
>
> With the design we discussed this should work because
> __builtin_with_access (or whatever) it reads:
>
> f = alloc(maximum_possible);
> f->count = 0;
>
> for (i; data_is_available() && i < maximum_possible; i++) {
> f->count ++;
> __builtin_with_access(f->buf, f->count)[i] = next_data_item();
> }
>
Yes, with the data flow, f->count should get the latest value of f->count.
>>
>>
>>>
>>> What we could potentially do is add restrictions so
>>> that the access to buf always has to go via x->buf
>>> or you get at least a warning.
>>
>> Are the following two restrictions to the user enough:
>>
>> 1. The access to buf should always go via x->buf,
>> no assignment to another independent pointer
>> and access buf through this new pointer.
>
> Yes, maybe. One could also try to be smarter.
>
> For example, one warn only when &f->buf is
> assigned to another pointer and one of the
> following conditions is fulfilled:
>
> - the pointer escapes from the local context
>
> - there is a store to f->counter in the
> local context that does not dominate &f->buf.
>
> Then Kees' example would work too in most cases.
I guess that we might need to come up with the list of concrete restrictions to
the user,
and list these restrictions in the user documentation.
Since the dynamic array support is quite important to the kernel (is this
true, Kees? ),
We might need to include such support into our design in the beginning.
>
> But I would probably wait until we have some
> initial experience with this feature.
You mean after we have an initial implementation of the “builtin_with_size”?
Yes, at this moment, I think that the “builtin_with_size” approach is the best
one.
Just some details need more thinking before the real implementation. -:)
Qing
>
> Martin
>
>> 2. User need to keep the synchronization between
>> the counter and the access to the buffer all the time.
