[Libguestfs] [PATCH libnbd 1/7] api: Add semi-private function for freeing persistent data.

[Eric Blake]

On 8/12/19 11:08 AM, Richard W.M. Jones wrote:
> This adds a C-only semi-private function for freeing various types of
> persistent data passed to libnbd.
> 
> There are some similarities with nbd_add_close_callback which we
> removed in commit 7f191b150b52ed50098976309a6af883d245fc56.
> ---

> +=head1 FREE CALLBACKS
> +
> +B<Note:> The API described in this section is only
> +available from C.  It is designed to help when writing
> +bindings to libnbd in other programming languages.
> +As such it is B<not> covered by the usual API stability
> +guarantee offered by other parts of the C API.  Use it with care.
> +
> +Some pointers passed to libnbd calls are saved in the
> +S<C<struct nbd_handle>>.  These include pointers to buffers
> +passed to C<nbd_aio_pread>, C<nbd_aio_pwrite>, etc.,
> +and pointers to the C<user_data> for callbacks.  If you
> +want to know when it is safe to free these objects then
> +you can register a free callback using:
> +
> + 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...

> +
> +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.

> +
> +where C<my_free> is a simple wrapper around the L<free(3)>
> +function (we are not using the extra C<user_data> pointer
> +in this case):
> +
> + void my_free (void *ptr, void *)
> + {
> +   free (ptr);
> + }

...without user_data, you wouldn't need a my_free wrapper, but could
just pass free() in the example.


> +++ b/lib/free.c
> @@ -0,0 +1,129 @@

> +/* This is not generated because we don't want to offer it to other
> + * programming languages.  Also it's a semi-private API liable to
> + * evolve in its exact semantics.
> + */
> +int
> +nbd_add_free_callback (struct nbd_handle *h, void *ptr,
> +                       nbd_free_callback cb, void *user_data)

At least the comment caveat gives us flexibility to change our mind on
whether to provide a user_data argument.

> +{
> +  int ret = -1;
> +  size_t i;
> +
> +  if (ptr == NULL)
> +    return 0;
> +
> +  nbd_internal_set_error_context ("nbd_add_free_callback");
> +  pthread_mutex_lock (&h->lock);
> +
> +  /* Extend the list of callbacks in the handle. */
> +  if (h->nr_free_callbacks >= h->alloc_free_callbacks) {
> +    size_t new_alloc;
> +    struct free_callback *new_callbacks;
> +
> +    if (h->alloc_free_callbacks == 0)
> +      new_alloc = 8;
> +    else
> +      new_alloc = 2 * h->alloc_free_callbacks;
> +
> +    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)

> +    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.

> +   */
> +  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.

> +      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?

> +  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->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).

> +  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.

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.

-- 
Eric Blake, Principal Software Engineer
Red Hat, Inc.           +1-919-301-3226
Virtualization:  qemu.org | libvirt.org

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 488 bytes
Desc: OpenPGP digital signature
URL: <http://listman.redhat.com/archives/libguestfs/attachments/20190812/6c5787ca/attachment.sig>