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

[Richard W.M. Jones]

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