src/vulkan/runtime/vk_sync_timeline.c - third_party/mesa - Git at Google

 /*
  * Copyright © 2021 Intel Corporation
  *
  * Permission is hereby granted, free of charge, to any person obtaining a
  * copy of this software and associated documentation files (the "Software"),
  * to deal in the Software without restriction, including without limitation
  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
  * and/or sell copies of the Software, and to permit persons to whom the
  * Software is furnished to do so, subject to the following conditions:
  *
  * The above copyright notice and this permission notice (including the next
  * paragraph) shall be included in all copies or substantial portions of the
  * Software.
  *
  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
  * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
  * IN THE SOFTWARE.
  */

 #include "vk_sync_timeline.h"

 #include <inttypes.h>

 #include "util/os_time.h"
 #include "util/timespec.h"

 #include "vk_alloc.h"
 #include "vk_device.h"
 #include "vk_log.h"

 static struct vk_sync_timeline *
 to_vk_sync_timeline(struct vk_sync *sync)
 {
    assert(sync->type->init == vk_sync_timeline_init);

    return container_of(sync, struct vk_sync_timeline, sync);
 }

 static struct vk_sync_timeline_state *
 to_vk_sync_timeline_state(struct vk_sync *sync)
 {
    struct vk_sync_timeline *timeline = to_vk_sync_timeline(sync);
    return timeline->state;
 }

 static void
 vk_sync_timeline_type_validate(const struct vk_sync_timeline_type *ttype)
 {
    ASSERTED const enum vk_sync_features req_features =
       VK_SYNC_FEATURE_BINARY |
       VK_SYNC_FEATURE_GPU_WAIT |
       VK_SYNC_FEATURE_GPU_MULTI_WAIT |
       VK_SYNC_FEATURE_CPU_WAIT |
       VK_SYNC_FEATURE_CPU_RESET;

    assert(!(req_features & ~ttype->point_sync_type->features));
 }

 static void
 vk_sync_timeline_state_ref(struct vk_sync_timeline_state *state)
 {
    p_atomic_inc(&state->refcount);
 }

 static void
 vk_sync_timeline_state_unref(struct vk_device *device,
                              struct vk_sync_timeline_state *state)
 {
    if (p_atomic_dec_return(&state->refcount))
       return;

    list_for_each_entry_safe(struct vk_sync_timeline_point, point,
                             &state->free_points, link) {
       list_del(&point->link);
       vk_sync_finish(device, &point->sync);
       vk_free(&device->alloc, point);
    }

    list_for_each_entry_safe(struct vk_sync_timeline_point, point,
                             &state->pending_points, link) {
       list_del(&point->link);
       vk_sync_finish(device, &point->sync);
       vk_free(&device->alloc, point);
    }

    u_cnd_monotonic_destroy(&state->cond);
    mtx_destroy(&state->mutex);
    vk_free(&device->alloc, state);
 }

 VkResult
 vk_sync_timeline_init(struct vk_device *device,
                       struct vk_sync *sync,
                       uint64_t initial_value)
 {
    struct vk_sync_timeline *timeline = to_vk_sync_timeline(sync);
    struct vk_sync_timeline_state *state;
    int ret;

    ASSERTED const struct vk_sync_timeline_type *ttype =
       container_of(timeline->sync.type, struct vk_sync_timeline_type, sync);
    vk_sync_timeline_type_validate(ttype);

    state = vk_zalloc(&device->alloc, sizeof(*state), 8,
                      VK_SYSTEM_ALLOCATION_SCOPE_DEVICE);
    if (!state)
       return vk_error(device, VK_ERROR_OUT_OF_HOST_MEMORY);

    ret = mtx_init(&state->mutex, mtx_plain);
    if (ret != thrd_success) {
       vk_free(&device->alloc, state);
       return vk_errorf(device, VK_ERROR_UNKNOWN, "mtx_init failed");
    }

    ret = u_cnd_monotonic_init(&state->cond);
    if (ret != thrd_success) {
       mtx_destroy(&state->mutex);
       vk_free(&device->alloc, state);
       return vk_errorf(device, VK_ERROR_UNKNOWN, "cnd_init failed");
    }

    state->highest_past = state->highest_pending = initial_value;
    list_inithead(&state->pending_points);
    list_inithead(&state->free_points);

    p_atomic_set(&state->refcount, 1);

    timeline->state = state;

    return VK_SUCCESS;
 }

 static VkResult
 vk_sync_timeline_gc_locked(struct vk_device *device,
                            struct vk_sync_timeline_state *state,
                            bool drain);

 static void
 vk_sync_timeline_finish(struct vk_device *device,
                         struct vk_sync *sync)
 {
    struct vk_sync_timeline_state *state = to_vk_sync_timeline_state(sync);

    /* We need to garbage collect to get rid of any pending points so that the
     * vk_sync_timeline_state_unref() at the end drops the final reference
     * held by the vk_sync_timeline. It's up to the client to ensure that
     * there are no vk_sync in-flight when this is called so this should get
     * rid of all pending time points. The only time point references left are
     * those held by waits or vk_queue_submit().
     */
    mtx_lock(&state->mutex);
    vk_sync_timeline_gc_locked(device, state, true);
    assert(list_is_empty(&state->pending_points));
    mtx_unlock(&state->mutex);

    vk_sync_timeline_state_unref(device, state);
 }

 static struct vk_sync_timeline_point *
 vk_sync_timeline_first_point(struct vk_sync_timeline_state *state)
 {
    struct vk_sync_timeline_point *point =
       list_first_entry(&state->pending_points,
                        struct vk_sync_timeline_point, link);

    assert(point->value <= state->highest_pending);
    assert(point->value > state->highest_past);

    return point;
 }

 static VkResult
 vk_sync_timeline_alloc_point_locked(struct vk_device *device,
                                     struct vk_sync_timeline *timeline,
                                     uint64_t value,
                                     struct vk_sync_timeline_point **point_out)
 {
    struct vk_sync_timeline_state *state = timeline->state;
    struct vk_sync_timeline_point *point;
    VkResult result;

    result = vk_sync_timeline_gc_locked(device, state, false);
    if (unlikely(result != VK_SUCCESS))
       return result;

    if (list_is_empty(&state->free_points)) {
       const struct vk_sync_timeline_type *ttype =
          container_of(timeline->sync.type, struct vk_sync_timeline_type, sync);
       const struct vk_sync_type *point_sync_type = ttype->point_sync_type;

       size_t size = offsetof(struct vk_sync_timeline_point, sync) +
                     point_sync_type->size;

       point = vk_zalloc(&device->alloc, size, 8,
                         VK_SYSTEM_ALLOCATION_SCOPE_DEVICE);
       if (!point)
          return vk_error(device, VK_ERROR_OUT_OF_HOST_MEMORY);

       point->timeline_state = state;

       result = vk_sync_init(device, &point->sync, point_sync_type,
                             0 /* flags */, 0 /* initial_value */);
       if (unlikely(result != VK_SUCCESS)) {
          vk_free(&device->alloc, point);
          return result;
       }
    } else {
       point = list_first_entry(&state->free_points,
                                struct vk_sync_timeline_point, link);

       if (point->sync.type->reset) {
          result = vk_sync_reset(device, &point->sync);
          if (unlikely(result != VK_SUCCESS))
             return result;
       }

       list_del(&point->link);
    }

    point->value = value;

    assert(point->refcount == 0);
    point->refcount++;

    *point_out = point;

    vk_sync_timeline_state_ref(state);

    return VK_SUCCESS;
 }

 VkResult
 vk_sync_timeline_alloc_point(struct vk_device *device,
                              struct vk_sync_timeline *timeline,
                              uint64_t value,
                              struct vk_sync_timeline_point **point_out)
 {
    VkResult result;

    mtx_lock(&timeline->state->mutex);
    result = vk_sync_timeline_alloc_point_locked(device, timeline, value, point_out);
    mtx_unlock(&timeline->state->mutex);

    return result;
 }

 static void
 vk_sync_timeline_ref_point_locked(struct vk_sync_timeline_point *point)
 {
    point->refcount++;
 }

 /* Returns true if this was the last reference to point.
  *
  * DO NOT call this helper directly. You should call vk_sync_timeline_unref_point_locked()
  * or vk_sync_timeline_point_unref() instead.
  */
 static bool
 vk_sync_timeline_unref_point_no_unref_state_locked(struct vk_sync_timeline_point *point)
 {
    struct vk_sync_timeline_state *state = point->timeline_state;

    assert(point->refcount > 0);
    point->refcount--;

    if (point->refcount > 0)
       return false;

    assert(point->refcount == 0);

    /* The pending list also takes a reference so this can't be pending */
    assert(!point->pending);
    list_add(&point->link, &state->free_points);

    return true;
 }

 static void
 vk_sync_timeline_unref_point_locked(struct vk_device *device,
                                     struct vk_sync_timeline_state *state,
                                     struct vk_sync_timeline_point *point)
 {
    /* The caller needs to have its own reference to the state, not just the
     * one implicit in point, because it's also holding the lock.
     */
    assert(p_atomic_read(&state->refcount) > 1);

    if (vk_sync_timeline_unref_point_no_unref_state_locked(point))
       vk_sync_timeline_state_unref(device, state);
 }

 void
 vk_sync_timeline_point_unref(struct vk_device *device,
                              struct vk_sync_timeline_point *point)
 {
    struct vk_sync_timeline_state *state = point->timeline_state;

    mtx_lock(&state->mutex);
    const bool last_ref =
       vk_sync_timeline_unref_point_no_unref_state_locked(point);
    mtx_unlock(&state->mutex);

    /* Drop the state reference outside the mutex so we don't free the state
     * and then try to unlock the mutex.
     */
    if (last_ref)
       vk_sync_timeline_state_unref(device, state);
 }

 static void
 vk_sync_timeline_complete_point_locked(struct vk_device *device,
                                        struct vk_sync_timeline_state *state,
                                        struct vk_sync_timeline_point *point)
 {
    if (!point->pending)
       return;

    assert(state->highest_past < point->value);
    state->highest_past = point->value;

    point->pending = false;
    list_del(&point->link);

    /* Drop the pending reference */
    vk_sync_timeline_unref_point_locked(device, state, point);
 }

 static VkResult
 vk_sync_timeline_gc_locked(struct vk_device *device,
                            struct vk_sync_timeline_state *state,
                            bool drain)
 {
    list_for_each_entry_safe(struct vk_sync_timeline_point, point,
                             &state->pending_points, link) {
       /* state->highest_pending is only incremented once submission has
        * happened. If this point has a greater serial, it means the point
        * hasn't been submitted yet.
        */
       if (point->value > state->highest_pending)
          return VK_SUCCESS;

       /* If someone is waiting on this time point, consider it busy and don't
        * try to recycle it. There's a slim possibility that it's no longer
        * busy by the time we look at it but we would be recycling it out from
        * under a waiter and that can lead to weird races.
        *
        * We walk the list in-order so if this time point is still busy so is
        * every following time point
        */
       assert(point->refcount > 0);
       if (point->refcount > 1 && !drain)
          return VK_SUCCESS;

       /* Garbage collect any signaled point. */
       VkResult result = vk_sync_wait(device, &point->sync, 0,
                                      VK_SYNC_WAIT_COMPLETE,
                                      0 /* abs_timeout_ns */);
       if (result == VK_TIMEOUT) {
          /* We walk the list in-order so if this time point is still busy so
           * is every following time point
           */
          return VK_SUCCESS;
       } else if (result != VK_SUCCESS) {
          return result;
       }

       vk_sync_timeline_complete_point_locked(device, state, point);
    }

    return VK_SUCCESS;
 }

 VkResult
 vk_sync_timeline_point_install(struct vk_device *device,
                                struct vk_sync_timeline_point *point)
 {
    struct vk_sync_timeline_state *state = point->timeline_state;

    mtx_lock(&state->mutex);

    assert(point->value > state->highest_pending);
    state->highest_pending = point->value;

    /* Adding to the pending list implicitly takes a reference but also this
     * function is documented to consume the reference to point so we don't
     * need to do anything to the reference count here.
     */
    point->pending = true;
    list_addtail(&point->link, &state->pending_points);

    int ret = u_cnd_monotonic_broadcast(&state->cond);

    mtx_unlock(&state->mutex);

    if (ret == thrd_error)
       return vk_errorf(device, VK_ERROR_UNKNOWN, "cnd_broadcast failed");

    return VK_SUCCESS;
 }

 static VkResult
 vk_sync_timeline_get_point_locked(struct vk_device *device,
                                   struct vk_sync_timeline_state *state,
                                   uint64_t wait_value,
                                   struct vk_sync_timeline_point **point_out)
 {
    if (state->highest_past >= wait_value) {
       /* Nothing to wait on */
       *point_out = NULL;
       return VK_SUCCESS;
    }

    list_for_each_entry(struct vk_sync_timeline_point, point,
                        &state->pending_points, link) {
       if (point->value >= wait_value) {
          vk_sync_timeline_ref_point_locked(point);
          *point_out = point;
          return VK_SUCCESS;
       }
    }

    return VK_NOT_READY;
 }

 VkResult
 vk_sync_timeline_get_point(struct vk_device *device,
                            struct vk_sync_timeline *timeline,
                            uint64_t wait_value,
                            struct vk_sync_timeline_point **point_out)
 {
    struct vk_sync_timeline_state *state = timeline->state;

    mtx_lock(&state->mutex);
    VkResult result = vk_sync_timeline_get_point_locked(device, state,
                                                        wait_value, point_out);
    mtx_unlock(&state->mutex);

    return result;
 }

 static VkResult
 vk_sync_timeline_signal_locked(struct vk_device *device,
                                struct vk_sync_timeline_state *state,
                                uint64_t value)
 {
    VkResult result = vk_sync_timeline_gc_locked(device, state, true);
    if (unlikely(result != VK_SUCCESS))
       return result;

    if (unlikely(value <= state->highest_past)) {
       return vk_device_set_lost(device, "Timeline values must only ever "
                                         "strictly increase.");
    }

    assert(list_is_empty(&state->pending_points));
    assert(state->highest_pending == state->highest_past);
    state->highest_pending = state->highest_past = value;

    int ret = u_cnd_monotonic_broadcast(&state->cond);
    if (ret == thrd_error)
       return vk_errorf(device, VK_ERROR_UNKNOWN, "cnd_broadcast failed");

    return VK_SUCCESS;
 }

 static VkResult
 vk_sync_timeline_signal(struct vk_device *device,
                         struct vk_sync *sync,
                         uint64_t value)
 {
    struct vk_sync_timeline_state *state = to_vk_sync_timeline_state(sync);

    mtx_lock(&state->mutex);
    VkResult result = vk_sync_timeline_signal_locked(device, state, value);
    mtx_unlock(&state->mutex);

    return result;
 }

 static VkResult
 vk_sync_timeline_get_value(struct vk_device *device,
                            struct vk_sync *sync,
                            uint64_t *value)
 {
    struct vk_sync_timeline_state *state = to_vk_sync_timeline_state(sync);

    mtx_lock(&state->mutex);
    VkResult result = vk_sync_timeline_gc_locked(device, state, true);
    mtx_unlock(&state->mutex);

    if (result != VK_SUCCESS)
       return result;

    *value = state->highest_past;

    return VK_SUCCESS;
 }

 static VkResult
 vk_sync_timeline_wait_locked(struct vk_device *device,
                              struct vk_sync_timeline_state *state,
                              uint64_t wait_value,
                              enum vk_sync_wait_flags wait_flags,
                              uint64_t abs_timeout_ns)
 {
    struct timespec abs_timeout_ts;
    timespec_from_nsec(&abs_timeout_ts, abs_timeout_ns);

    /* Wait on the queue_submit condition variable until the timeline has a
     * time point pending that's at least as high as wait_value.
     */
    while (state->highest_pending < wait_value) {
       int ret = u_cnd_monotonic_timedwait(&state->cond, &state->mutex,
                                           &abs_timeout_ts);
       if (ret == thrd_timedout)
          return VK_TIMEOUT;

       if (ret != thrd_success)
          return vk_errorf(device, VK_ERROR_UNKNOWN, "cnd_timedwait failed");
    }

    if (wait_flags & VK_SYNC_WAIT_PENDING)
       return VK_SUCCESS;

    VkResult result = vk_sync_timeline_gc_locked(device, state, false);
    if (result != VK_SUCCESS)
       return result;

    while (state->highest_past < wait_value) {
       struct vk_sync_timeline_point *point = vk_sync_timeline_first_point(state);

       /* Drop the lock while we wait. */
       vk_sync_timeline_ref_point_locked(point);
       mtx_unlock(&state->mutex);

       result = vk_sync_wait(device, &point->sync, 0,
                             VK_SYNC_WAIT_COMPLETE,
                             abs_timeout_ns);

       /* Pick the mutex back up */
       mtx_lock(&state->mutex);
       vk_sync_timeline_unref_point_locked(device, state, point);

       /* This covers both VK_TIMEOUT and VK_ERROR_DEVICE_LOST */
       if (result != VK_SUCCESS)
          return result;

       vk_sync_timeline_complete_point_locked(device, state, point);
    }

    return VK_SUCCESS;
 }

 static VkResult
 vk_sync_timeline_wait(struct vk_device *device,
                       struct vk_sync *sync,
                       uint64_t wait_value,
                       enum vk_sync_wait_flags wait_flags,
                       uint64_t abs_timeout_ns)
 {
    struct vk_sync_timeline_state *state = to_vk_sync_timeline_state(sync);

    mtx_lock(&state->mutex);
    VkResult result = vk_sync_timeline_wait_locked(device, state,
                                                   wait_value, wait_flags,
                                                   abs_timeout_ns);
    mtx_unlock(&state->mutex);

    return result;
 }

 struct vk_sync_timeline_type
 vk_sync_timeline_get_type(const struct vk_sync_type *point_sync_type)
 {
    return (struct vk_sync_timeline_type) {
       .sync = {
          .size = sizeof(struct vk_sync_timeline),
          .features = VK_SYNC_FEATURE_TIMELINE |
                      VK_SYNC_FEATURE_GPU_WAIT |
                      VK_SYNC_FEATURE_CPU_WAIT |
                      VK_SYNC_FEATURE_CPU_SIGNAL |
                      VK_SYNC_FEATURE_WAIT_ANY |
                      VK_SYNC_FEATURE_WAIT_PENDING,
          .init = vk_sync_timeline_init,
          .finish = vk_sync_timeline_finish,
          .signal = vk_sync_timeline_signal,
          .get_value = vk_sync_timeline_get_value,
          .wait = vk_sync_timeline_wait,
       },
       .point_sync_type = point_sync_type,
    };
 }
	/*
	* Copyright © 2021 Intel Corporation
	*
	* Permission is hereby granted, free of charge, to any person obtaining a
	* copy of this software and associated documentation files (the "Software"),
	* to deal in the Software without restriction, including without limitation
	* the rights to use, copy, modify, merge, publish, distribute, sublicense,
	* and/or sell copies of the Software, and to permit persons to whom the
	* Software is furnished to do so, subject to the following conditions:
	*
	* The above copyright notice and this permission notice (including the next
	* paragraph) shall be included in all copies or substantial portions of the
	* Software.
	*
	* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
	* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
	* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
	* THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
	* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
	* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
	* IN THE SOFTWARE.
	*/

	#include "vk_sync_timeline.h"

	#include <inttypes.h>

	#include "util/os_time.h"
	#include "util/timespec.h"

	#include "vk_alloc.h"
	#include "vk_device.h"
	#include "vk_log.h"

	static struct vk_sync_timeline *
	to_vk_sync_timeline(struct vk_sync *sync)
	{
	assert(sync->type->init == vk_sync_timeline_init);

	return container_of(sync, struct vk_sync_timeline, sync);
	}

	static struct vk_sync_timeline_state *
	to_vk_sync_timeline_state(struct vk_sync *sync)
	{
	struct vk_sync_timeline *timeline = to_vk_sync_timeline(sync);
	return timeline->state;
	}

	static void
	vk_sync_timeline_type_validate(const struct vk_sync_timeline_type *ttype)
	{
	ASSERTED const enum vk_sync_features req_features =
	VK_SYNC_FEATURE_BINARY \|
	VK_SYNC_FEATURE_GPU_WAIT \|
	VK_SYNC_FEATURE_GPU_MULTI_WAIT \|
	VK_SYNC_FEATURE_CPU_WAIT \|
	VK_SYNC_FEATURE_CPU_RESET;

	assert(!(req_features & ~ttype->point_sync_type->features));
	}

	static void
	vk_sync_timeline_state_ref(struct vk_sync_timeline_state *state)
	{
	p_atomic_inc(&state->refcount);
	}

	static void
	vk_sync_timeline_state_unref(struct vk_device *device,
	struct vk_sync_timeline_state *state)
	{
	if (p_atomic_dec_return(&state->refcount))
	return;

	list_for_each_entry_safe(struct vk_sync_timeline_point, point,
	&state->free_points, link) {
	list_del(&point->link);
	vk_sync_finish(device, &point->sync);
	vk_free(&device->alloc, point);
	}

	list_for_each_entry_safe(struct vk_sync_timeline_point, point,
	&state->pending_points, link) {
	list_del(&point->link);
	vk_sync_finish(device, &point->sync);
	vk_free(&device->alloc, point);
	}

	u_cnd_monotonic_destroy(&state->cond);
	mtx_destroy(&state->mutex);
	vk_free(&device->alloc, state);
	}

	VkResult
	vk_sync_timeline_init(struct vk_device *device,
	struct vk_sync *sync,
	uint64_t initial_value)
	{
	struct vk_sync_timeline *timeline = to_vk_sync_timeline(sync);
	struct vk_sync_timeline_state *state;
	int ret;

	ASSERTED const struct vk_sync_timeline_type *ttype =
	container_of(timeline->sync.type, struct vk_sync_timeline_type, sync);
	vk_sync_timeline_type_validate(ttype);

	state = vk_zalloc(&device->alloc, sizeof(*state), 8,
	VK_SYSTEM_ALLOCATION_SCOPE_DEVICE);
	if (!state)
	return vk_error(device, VK_ERROR_OUT_OF_HOST_MEMORY);

	ret = mtx_init(&state->mutex, mtx_plain);
	if (ret != thrd_success) {
	vk_free(&device->alloc, state);
	return vk_errorf(device, VK_ERROR_UNKNOWN, "mtx_init failed");
	}

	ret = u_cnd_monotonic_init(&state->cond);
	if (ret != thrd_success) {
	mtx_destroy(&state->mutex);
	vk_free(&device->alloc, state);
	return vk_errorf(device, VK_ERROR_UNKNOWN, "cnd_init failed");
	}

	state->highest_past = state->highest_pending = initial_value;
	list_inithead(&state->pending_points);
	list_inithead(&state->free_points);

	p_atomic_set(&state->refcount, 1);

	timeline->state = state;

	return VK_SUCCESS;
	}

	static VkResult
	vk_sync_timeline_gc_locked(struct vk_device *device,
	struct vk_sync_timeline_state *state,
	bool drain);

	static void
	vk_sync_timeline_finish(struct vk_device *device,
	struct vk_sync *sync)
	{
	struct vk_sync_timeline_state *state = to_vk_sync_timeline_state(sync);

	/* We need to garbage collect to get rid of any pending points so that the
	* vk_sync_timeline_state_unref() at the end drops the final reference
	* held by the vk_sync_timeline. It's up to the client to ensure that
	* there are no vk_sync in-flight when this is called so this should get
	* rid of all pending time points. The only time point references left are
	* those held by waits or vk_queue_submit().
	*/
	mtx_lock(&state->mutex);
	vk_sync_timeline_gc_locked(device, state, true);
	assert(list_is_empty(&state->pending_points));
	mtx_unlock(&state->mutex);

	vk_sync_timeline_state_unref(device, state);
	}

	static struct vk_sync_timeline_point *
	vk_sync_timeline_first_point(struct vk_sync_timeline_state *state)
	{
	struct vk_sync_timeline_point *point =
	list_first_entry(&state->pending_points,
	struct vk_sync_timeline_point, link);

	assert(point->value <= state->highest_pending);
	assert(point->value > state->highest_past);

	return point;
	}

	static VkResult
	vk_sync_timeline_alloc_point_locked(struct vk_device *device,
	struct vk_sync_timeline *timeline,
	uint64_t value,
	struct vk_sync_timeline_point **point_out)
	{
	struct vk_sync_timeline_state *state = timeline->state;
	struct vk_sync_timeline_point *point;
	VkResult result;

	result = vk_sync_timeline_gc_locked(device, state, false);
	if (unlikely(result != VK_SUCCESS))
	return result;

	if (list_is_empty(&state->free_points)) {
	const struct vk_sync_timeline_type *ttype =
	container_of(timeline->sync.type, struct vk_sync_timeline_type, sync);
	const struct vk_sync_type *point_sync_type = ttype->point_sync_type;

	size_t size = offsetof(struct vk_sync_timeline_point, sync) +
	point_sync_type->size;

	point = vk_zalloc(&device->alloc, size, 8,
	VK_SYSTEM_ALLOCATION_SCOPE_DEVICE);
	if (!point)
	return vk_error(device, VK_ERROR_OUT_OF_HOST_MEMORY);

	point->timeline_state = state;

	result = vk_sync_init(device, &point->sync, point_sync_type,
	0 /* flags /, 0 / initial_value */);
	if (unlikely(result != VK_SUCCESS)) {
	vk_free(&device->alloc, point);
	return result;
	}
	} else {
	point = list_first_entry(&state->free_points,
	struct vk_sync_timeline_point, link);

	if (point->sync.type->reset) {
	result = vk_sync_reset(device, &point->sync);
	if (unlikely(result != VK_SUCCESS))
	return result;
	}

	list_del(&point->link);
	}

	point->value = value;

	assert(point->refcount == 0);
	point->refcount++;

	*point_out = point;

	vk_sync_timeline_state_ref(state);

	return VK_SUCCESS;
	}

	VkResult
	vk_sync_timeline_alloc_point(struct vk_device *device,
	struct vk_sync_timeline *timeline,
	uint64_t value,
	struct vk_sync_timeline_point **point_out)
	{
	VkResult result;

	mtx_lock(&timeline->state->mutex);
	result = vk_sync_timeline_alloc_point_locked(device, timeline, value, point_out);
	mtx_unlock(&timeline->state->mutex);

	return result;
	}

	static void
	vk_sync_timeline_ref_point_locked(struct vk_sync_timeline_point *point)
	{
	point->refcount++;
	}

	/* Returns true if this was the last reference to point.
	*
	* DO NOT call this helper directly. You should call vk_sync_timeline_unref_point_locked()
	* or vk_sync_timeline_point_unref() instead.
	*/
	static bool
	vk_sync_timeline_unref_point_no_unref_state_locked(struct vk_sync_timeline_point *point)
	{
	struct vk_sync_timeline_state *state = point->timeline_state;

	assert(point->refcount > 0);
	point->refcount--;

	if (point->refcount > 0)
	return false;

	assert(point->refcount == 0);

	/* The pending list also takes a reference so this can't be pending */
	assert(!point->pending);
	list_add(&point->link, &state->free_points);

	return true;
	}

	static void
	vk_sync_timeline_unref_point_locked(struct vk_device *device,
	struct vk_sync_timeline_state *state,
	struct vk_sync_timeline_point *point)
	{
	/* The caller needs to have its own reference to the state, not just the
	* one implicit in point, because it's also holding the lock.
	*/
	assert(p_atomic_read(&state->refcount) > 1);

	if (vk_sync_timeline_unref_point_no_unref_state_locked(point))
	vk_sync_timeline_state_unref(device, state);
	}

	void
	vk_sync_timeline_point_unref(struct vk_device *device,
	struct vk_sync_timeline_point *point)
	{
	struct vk_sync_timeline_state *state = point->timeline_state;

	mtx_lock(&state->mutex);
	const bool last_ref =
	vk_sync_timeline_unref_point_no_unref_state_locked(point);
	mtx_unlock(&state->mutex);

	/* Drop the state reference outside the mutex so we don't free the state
	* and then try to unlock the mutex.
	*/
	if (last_ref)
	vk_sync_timeline_state_unref(device, state);
	}

	static void
	vk_sync_timeline_complete_point_locked(struct vk_device *device,
	struct vk_sync_timeline_state *state,
	struct vk_sync_timeline_point *point)
	{
	if (!point->pending)
	return;

	assert(state->highest_past < point->value);
	state->highest_past = point->value;

	point->pending = false;
	list_del(&point->link);

	/* Drop the pending reference */
	vk_sync_timeline_unref_point_locked(device, state, point);
	}

	static VkResult
	vk_sync_timeline_gc_locked(struct vk_device *device,
	struct vk_sync_timeline_state *state,
	bool drain)
	{
	list_for_each_entry_safe(struct vk_sync_timeline_point, point,
	&state->pending_points, link) {
	/* state->highest_pending is only incremented once submission has
	* happened. If this point has a greater serial, it means the point
	* hasn't been submitted yet.
	*/
	if (point->value > state->highest_pending)
	return VK_SUCCESS;

	/* If someone is waiting on this time point, consider it busy and don't
	* try to recycle it. There's a slim possibility that it's no longer
	* busy by the time we look at it but we would be recycling it out from
	* under a waiter and that can lead to weird races.
	*
	* We walk the list in-order so if this time point is still busy so is
	* every following time point
	*/
	assert(point->refcount > 0);
	if (point->refcount > 1 && !drain)
	return VK_SUCCESS;

	/* Garbage collect any signaled point. */
	VkResult result = vk_sync_wait(device, &point->sync, 0,
	VK_SYNC_WAIT_COMPLETE,
	0 /* abs_timeout_ns */);
	if (result == VK_TIMEOUT) {
	/* We walk the list in-order so if this time point is still busy so
	* is every following time point
	*/
	return VK_SUCCESS;
	} else if (result != VK_SUCCESS) {
	return result;
	}

	vk_sync_timeline_complete_point_locked(device, state, point);
	}

	return VK_SUCCESS;
	}

	VkResult
	vk_sync_timeline_point_install(struct vk_device *device,
	struct vk_sync_timeline_point *point)
	{
	struct vk_sync_timeline_state *state = point->timeline_state;

	mtx_lock(&state->mutex);

	assert(point->value > state->highest_pending);
	state->highest_pending = point->value;

	/* Adding to the pending list implicitly takes a reference but also this
	* function is documented to consume the reference to point so we don't
	* need to do anything to the reference count here.
	*/
	point->pending = true;
	list_addtail(&point->link, &state->pending_points);

	int ret = u_cnd_monotonic_broadcast(&state->cond);

	mtx_unlock(&state->mutex);

	if (ret == thrd_error)
	return vk_errorf(device, VK_ERROR_UNKNOWN, "cnd_broadcast failed");

	return VK_SUCCESS;
	}

	static VkResult
	vk_sync_timeline_get_point_locked(struct vk_device *device,
	struct vk_sync_timeline_state *state,
	uint64_t wait_value,
	struct vk_sync_timeline_point **point_out)
	{
	if (state->highest_past >= wait_value) {
	/* Nothing to wait on */
	*point_out = NULL;
	return VK_SUCCESS;
	}

	list_for_each_entry(struct vk_sync_timeline_point, point,
	&state->pending_points, link) {
	if (point->value >= wait_value) {
	vk_sync_timeline_ref_point_locked(point);
	*point_out = point;
	return VK_SUCCESS;
	}
	}

	return VK_NOT_READY;
	}

	VkResult
	vk_sync_timeline_get_point(struct vk_device *device,
	struct vk_sync_timeline *timeline,
	uint64_t wait_value,
	struct vk_sync_timeline_point **point_out)
	{
	struct vk_sync_timeline_state *state = timeline->state;

	mtx_lock(&state->mutex);
	VkResult result = vk_sync_timeline_get_point_locked(device, state,
	wait_value, point_out);
	mtx_unlock(&state->mutex);

	return result;
	}

	static VkResult
	vk_sync_timeline_signal_locked(struct vk_device *device,
	struct vk_sync_timeline_state *state,
	uint64_t value)
	{
	VkResult result = vk_sync_timeline_gc_locked(device, state, true);
	if (unlikely(result != VK_SUCCESS))
	return result;

	if (unlikely(value <= state->highest_past)) {
	return vk_device_set_lost(device, "Timeline values must only ever "
	"strictly increase.");
	}

	assert(list_is_empty(&state->pending_points));
	assert(state->highest_pending == state->highest_past);
	state->highest_pending = state->highest_past = value;

	int ret = u_cnd_monotonic_broadcast(&state->cond);
	if (ret == thrd_error)
	return vk_errorf(device, VK_ERROR_UNKNOWN, "cnd_broadcast failed");

	return VK_SUCCESS;
	}

	static VkResult
	vk_sync_timeline_signal(struct vk_device *device,
	struct vk_sync *sync,
	uint64_t value)
	{
	struct vk_sync_timeline_state *state = to_vk_sync_timeline_state(sync);

	mtx_lock(&state->mutex);
	VkResult result = vk_sync_timeline_signal_locked(device, state, value);
	mtx_unlock(&state->mutex);

	return result;
	}

	static VkResult
	vk_sync_timeline_get_value(struct vk_device *device,
	struct vk_sync *sync,
	uint64_t *value)
	{
	struct vk_sync_timeline_state *state = to_vk_sync_timeline_state(sync);

	mtx_lock(&state->mutex);
	VkResult result = vk_sync_timeline_gc_locked(device, state, true);
	mtx_unlock(&state->mutex);

	if (result != VK_SUCCESS)
	return result;

	*value = state->highest_past;

	return VK_SUCCESS;
	}

	static VkResult
	vk_sync_timeline_wait_locked(struct vk_device *device,
	struct vk_sync_timeline_state *state,
	uint64_t wait_value,
	enum vk_sync_wait_flags wait_flags,
	uint64_t abs_timeout_ns)
	{
	struct timespec abs_timeout_ts;
	timespec_from_nsec(&abs_timeout_ts, abs_timeout_ns);

	/* Wait on the queue_submit condition variable until the timeline has a
	* time point pending that's at least as high as wait_value.
	*/
	while (state->highest_pending < wait_value) {
	int ret = u_cnd_monotonic_timedwait(&state->cond, &state->mutex,
	&abs_timeout_ts);
	if (ret == thrd_timedout)
	return VK_TIMEOUT;

	if (ret != thrd_success)
	return vk_errorf(device, VK_ERROR_UNKNOWN, "cnd_timedwait failed");
	}

	if (wait_flags & VK_SYNC_WAIT_PENDING)
	return VK_SUCCESS;

	VkResult result = vk_sync_timeline_gc_locked(device, state, false);
	if (result != VK_SUCCESS)
	return result;

	while (state->highest_past < wait_value) {
	struct vk_sync_timeline_point *point = vk_sync_timeline_first_point(state);

	/* Drop the lock while we wait. */
	vk_sync_timeline_ref_point_locked(point);
	mtx_unlock(&state->mutex);

	result = vk_sync_wait(device, &point->sync, 0,
	VK_SYNC_WAIT_COMPLETE,
	abs_timeout_ns);

	/* Pick the mutex back up */
	mtx_lock(&state->mutex);
	vk_sync_timeline_unref_point_locked(device, state, point);

	/* This covers both VK_TIMEOUT and VK_ERROR_DEVICE_LOST */
	if (result != VK_SUCCESS)
	return result;

	vk_sync_timeline_complete_point_locked(device, state, point);
	}

	return VK_SUCCESS;
	}

	static VkResult
	vk_sync_timeline_wait(struct vk_device *device,
	struct vk_sync *sync,
	uint64_t wait_value,
	enum vk_sync_wait_flags wait_flags,
	uint64_t abs_timeout_ns)
	{
	struct vk_sync_timeline_state *state = to_vk_sync_timeline_state(sync);

	mtx_lock(&state->mutex);
	VkResult result = vk_sync_timeline_wait_locked(device, state,
	wait_value, wait_flags,
	abs_timeout_ns);
	mtx_unlock(&state->mutex);

	return result;
	}

	struct vk_sync_timeline_type
	vk_sync_timeline_get_type(const struct vk_sync_type *point_sync_type)
	{
	return (struct vk_sync_timeline_type) {
	.sync = {
	.size = sizeof(struct vk_sync_timeline),
	.features = VK_SYNC_FEATURE_TIMELINE \|
	VK_SYNC_FEATURE_GPU_WAIT \|
	VK_SYNC_FEATURE_CPU_WAIT \|
	VK_SYNC_FEATURE_CPU_SIGNAL \|
	VK_SYNC_FEATURE_WAIT_ANY \|
	VK_SYNC_FEATURE_WAIT_PENDING,
	.init = vk_sync_timeline_init,
	.finish = vk_sync_timeline_finish,
	.signal = vk_sync_timeline_signal,
	.get_value = vk_sync_timeline_get_value,
	.wait = vk_sync_timeline_wait,
	},
	.point_sync_type = point_sync_type,
	};
	}