On Mon, Aug 12, 2019 at 11:29:10AM -0500, Eric Blake wrote:
On 8/12/19 11:08 AM, Richard W.M. Jones wrote:
+ typedef void (*nbd_free_callback) (void *ptr, void *user_data); + int nbd_add_free_callback (struct nbd_handle *h, + void *ptr, + nbd_free_callback cb, + void *user_data);
Do we want to insist on a user_data argument? Libvirt, for example, states that free callbacks are passed only the pointer to be freed (as you can already pack whatever you need into that pointer alone, rather than needing yet another void *user_data); if we do not take a user_data here, then...
Indeed, and that was my original implementation, and it would be usable in the simple case (free). However it doesn't work for OCaml buffers (nor for Python). In OCaml we need to free the GC root, but that is separate from the buffer pointer. The generated code for an OCaml persistent buffers eventually looks like this: /* The function may save a reference to the Buffer, so we * must treat it as a possible GC root. */ value *buf_user_data; buf_user_data = malloc (sizeof (value)); if (buf_user_data == NULL) caml_raise_out_of_memory (); *buf_user_data = bufv; caml_register_generational_global_root (buf_user_data); struct nbd_buffer *buf_buf = NBD_buffer_val (bufv); const void *buf = buf_buf->data; size_t count = buf_buf->len; if (nbd_add_free_callback (h, (void *)buf, free_root, buf_user_data) == -1) caml_raise_out_of_memory (); Notice that the free_root function needs the pointer to the GC root, but you can't get to that from the buffer pointer. A similar problem will exist in Python, but I've not got around to writing that code yet.
+C<ptr> is a pointer to the object (ie. the buffer or +callback C<user_data>). C<cb (ptr)> is called when libnbd
As written, your patch uses C<cb (ptr, user_data)>, so either this text is wrong, or you really don't need user_data.
Yes it should be cb (ptr, user_data). I'll tighten it up because there are now two user_datas.
+ new_callbacks = realloc (h->free_callbacks, + sizeof (struct free_callback) * new_alloc);
Should we start relying on reallocarray() to guarantee no multiplication overflow? (Not yet in POSIX, but it has been proposed: http://austingroupbugs.net/view.php?id=1218)
I guess - didn't know about it. Seems like it's not available in glibc yet?
+ if (new_callbacks == NULL) { + set_error (errno, "realloc"); + goto out; + } + h->alloc_free_callbacks = new_alloc; + h->free_callbacks = new_callbacks; + } + + /* Need to keep the list sorted by pointer so we can use bsearch. + * Insert the new entry before the i'th entry. + * + * Note the same pointer can be added multiple times (eg. if a + * buffer is shared between commands), and that is not a bug. Which + * free function is called is undefined, but they should all be + * called eventually.
or in other words, if the free function is actually a reference counter that only does something interesting when the count reaches 0, then things still work.
Yes this is another reason why this API is trickier to use than it seems. But this is really necessary if you share a buffer between several AIO calls as I discovered during implementation.
+ */ + for (i = 0; i < h->nr_free_callbacks; ++i) { + if (ptr <= h->free_callbacks[i].ptr)
Comparing 2 pointers that are not allocated as part of the same array is undefined in C. To be safe, you're better off writing this as:
if ((intptr_t)ptr <= (intptr_t)h->free_callbacks[i].ptr)
or even storing intptr_t rather than void* in your list of pointers needing callbacks.
OK.
+ break; + }
This is a linear search O(n) for where to insert. Why not bsearch() for O(log n), particularly since you document your intent to use bsearch() for later lookups?
Yes indeed, good idea!
+ memmove (&h->free_callbacks[i+1], &h->free_callbacks[i], + (h->nr_free_callbacks - i) * sizeof (struct free_callback));
Hmm - the use of memmove() is O(n); we'd need a different data structure (for example red-black tree or hash table) if we wanted list manipulations to not be the chokepoint. So, as long as you are already stuck with an O(n) list manipulation, using O(n) lookup is not making the problem any worse.
h->nr_free_callbacks is actually reasonably small in real code (usually <= 20). It's somewhat related to the number of commands in flight multiplied by a small constant.
+ + h->free_callbacks[i].ptr = ptr; + h->free_callbacks[i].cb = cb; + h->free_callbacks[i].user_data = user_data; + h->nr_free_callbacks++; + + ret = 0; + out: + pthread_mutex_unlock (&h->lock); + return ret; +} + +static int +compare_free_callbacks (const void *v1, const void *v2) +{ + const void *ptr = v1; + const struct free_callback *cb = v2; + + if (ptr < cb->ptr) return -1; + else if (ptr > cb->ptr) return 1;
Again, undefined in C; comparing intptr_t is defined, but direct comparison of unrelated pointers could cause a compiler to mis-optimize (even if it happens to currently work in practice).
OK. We could store the pointers in the struct as intptr_t ?
+ else return 0; +} + +/* Called before the library frees 'ptr', where 'ptr' is something + * that might potentially be associated with a free callback. This is + * called often so must be fast. + */ +void +nbd_internal_free_callback (struct nbd_handle *h, void *ptr) +{ + struct free_callback *free_cb; + + if (ptr == NULL) + return; + + free_cb = bsearch (ptr, h->free_callbacks, h->nr_free_callbacks, + sizeof (struct free_callback), + compare_free_callbacks);
Here, you've got O(log n) lookup.
+ if (free_cb) { + assert (ptr == free_cb->ptr); + + free_cb->cb (ptr, free_cb->user_data); + + /* Remove it from the free list. */ + memmove (free_cb, free_cb+1, + sizeof (struct free_callback) * + (&h->free_callbacks[h->nr_free_callbacks] - (free_cb+1)));
but then slow it down with O(n) list manipulation.
Right, but only when we actually call the callback. For C callers we will basically never use this. h->nr_free_callbacks will be 0 and we will do a frequent bsearch on a zero-sized array. It's only expected to be used from other programming languages.
I'm still not sold on whether this is any better than our existing completion callbacks coupled with VALID|FREE (where at least we didn't suffer from O(n) lookups); or whether we want to instead explore taking an explicit free function pointer as part of a C closure (that is, each Closure maps to a three-tuple of C arguments for main function, free function, and user_data). But as you said in the cover letter, having the whole series to review will let us choose between our options, so I'll see what the rest of the series is able to accomplish with this.
I think we shouldn't worry about whether the implementation is efficient since we can always improve that based on feedback from perf. It's really about whether this is a better API for freeing or not. Rich. -- Richard Jones, Virtualization Group, Red Hat http://people.redhat.com/~rjones Read my programming and virtualization blog: http://rwmj.wordpress.com Fedora Windows cross-compiler. Compile Windows programs, test, and build Windows installers. Over 100 libraries supported. http://fedoraproject.org/wiki/MinGW