Re: pserialize-safe queue(3) alternative

[Taylor R Campbell <campbell+netbsd-tech-kern%mumble.net@localhost>]

   Date: Sun, 3 Apr 2016 18:20:06 +0000
   From: Taylor R Campbell <campbell+netbsd-tech-kern%mumble.net@localhost>

   The attached pslist.h implements a pserialize-safe alternative to the
   LIST_* operations in queue(3), with example use in pslist.c:

...actually attached, this time for real!

/*	$NetBSD$	*/

/*-
 * Copyright (c) 2016 The NetBSD Foundation, Inc.
 * All rights reserved.
 *
 * This code is derived from software contributed to The NetBSD Foundation
 * by Taylor R. Campbell.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 */

#ifndef	_SYS_PSLIST_H
#define	_SYS_PSLIST_H

#include <sys/param.h>
#include <sys/atomic.h>

struct pslist_head;
struct pslist_entry;

struct pslist_head {
	struct pslist_entry *plh_first;
};

struct pslist_entry {
	struct pslist_entry **ple_prevp;
	struct pslist_entry *ple_next;
};

/*
 * Initialization.
 */

static inline void
pslist_init(struct pslist_head *head)
{

	head->plh_first = NULL;
}

/*
 * Writer operations.  Caller must have exclusive access to the list.
 */

static inline void
pslist_writer_insert_head(struct pslist_head *head, struct pslist_entry *new)
{

	new->ple_prevp = &head->plh_first;
	new->ple_next = head->plh_first;
	membar_producer();
	head->plh_first = new;
}

static inline void
pslist_writer_insert_before(struct pslist_entry *entry,
    struct pslist_entry *new)
{

	new->ple_prevp = entry->ple_prevp;
	new->ple_next = entry;
	membar_producer();
	*entry->ple_prevp = new;
	entry->ple_prevp = &new->ple_next;
}

static inline void
pslist_writer_insert_after(struct pslist_entry *entry,
    struct pslist_entry *new)
{

	new->ple_prevp = &entry->ple_next;
	new->ple_next = entry->ple_next;
	membar_producer();
	entry->ple_next = new;
}

static inline void
pslist_writer_remove(struct pslist_entry *entry)
{

	*entry->ple_prevp = entry->ple_next;
	entry->ple_prevp = NULL; /* poison */
}

static inline struct pslist_entry *
pslist_writer_first(struct pslist_head *head)
{

	return head->plh_first;
}

static inline struct pslist_entry *
pslist_writer_next(struct pslist_entry *entry)
{

	return entry->ple_next;
}

static inline void *
_pslist_writer_first_container(struct pslist_head *head, ptrdiff_t offset)
{
	struct pslist_entry *first = head->plh_first;

	return (first == NULL ? NULL : (char *)first - offset);
}

static inline void *
_pslist_writer_next_container(struct pslist_entry *entry, ptrdiff_t offset)
{
	struct pslist_entry *next = entry->ple_next;

	return (entry == NULL ? NULL : (char *)entry - offset);
}

/*
 * Reader operations.  Caller must block pserialize_perform or
 * equivalent and be bound to a CPU.
 */

static inline struct pslist_entry *
pslist_reader_first(struct pslist_head *head)
{
	struct pslist_entry *first = head->plh_first;

	if (first != NULL)
		membar_datadep_consumer();

	return first;
}

static inline struct pslist_entry *
pslist_reader_next(struct pslist_entry *entry)
{
	struct pslist_entry *next = entry->ple_next;

	if (next != NULL)
		membar_datadep_consumer();

	return next;
}

static inline void *
_pslist_reader_first_container(struct pslist_head *head, ptrdiff_t offset)
{
	struct pslist_entry *first = head->plh_first;

	if (first == NULL)
		return NULL;
	membar_datadep_consumer();

	return (char *)first - offset;
}

static inline void *
_pslist_reader_next_container(struct pslist_entry *entry, ptrdiff_t offset)
{
	struct pslist_entry *next = entry->ple_next;

	if (entry == NULL)
		return NULL;
	membar_datadep_consumer();

	return (char *)next - offset;
}

/*
 * Type-safe macros for convenience.
 */

#ifdef __COVERITY__
#define	_PSLIST_VALIDATE_PTRS(P, Q)		0
#define	_PSLIST_VALIDATE_CONTAINER(P, T, F)	0
#else
#define	_PSLIST_VALIDATE_PTRS(P, Q)					      \
	(0 * sizeof((P) - (Q)) * sizeof(*(P)) * sizeof(*(Q)))
#define	_PSLIST_VALIDATE_CONTAINER(P, T, F)				      \
	(0 * sizeof((P) - &((T *)(((char *)(P)) - offsetof(T, F)))->F))
#endif

#define	PSLIST_INITIALIZER(H)		{ .plh_first = NULL }

#define	PSLIST_INIT(H)			pslist_init((H))

#define	PSLIST_WRITER_INSERT_HEAD(H, V, F)				      \
	pslist_writer_insert_head((H), &(V)->F)
#define	PSLIST_WRITER_INSERT_BEFORE(E, N, F)				      \
	pslist_writer_insert_before(&(E)->F + _PSLIST_VALIDATE_PTRS(E, N),    \
	    &(N)->F)
#define	PSLIST_WRITER_INSERT_AFTER(E, N, F)				      \
	pslist_writer_insert_after(&(E)->F + _PSLIST_VALIDATE_PTRS(E, N),     \
	    &(N)->F)
#define	PSLIST_WRITER_REMOVE(E, F)					      \
	pslist_writer_remove(&(E)->F)
#define	PSLIST_WRITER_FIRST(H, T, F)					      \
	((T *)(_pslist_writer_first_container((H), offsetof(T, F))) +	      \
	    _PSLIST_VALIDATE_CONTAINER(pslist_first(H), T, F))
#define	PSLIST_WRITER_NEXT(V, T, F)					      \
	((T *)(_pslist_writer_next_container(&(V)->F, offsetof(T, F))) +      \
	    _PSLIST_VALIDATE_CONTAINER(pslist_next(&(V)->F), T, F))
#define	PSLIST_WRITER_FOREACH(V, H, T, F)				      \
	for ((V) = PSLIST_WRITER_FIRST((H), T, F);			      \
		(V) != NULL;						      \
		(V) = PSLIST_WRITER_NEXT((V), T, F))

#define	PSLIST_READER_FIRST(H, T, F)					      \
	((T *)(_pslist_reader_first_container((H), offsetof(T, F))) +	      \
	    _PSLIST_VALIDATE_CONTAINER(pslist_first(H), T, F))
#define	PSLIST_READER_NEXT(V, T, F)					      \
	((T *)(_pslist_reader_next_container(&(V)->F, offsetof(T, F))) +      \
	    _PSLIST_VALIDATE_CONTAINER(pslist_next(&(V)->F), T, F))
#define	PSLIST_READER_FOREACH(V, H, T, F)				      \
	for ((V) = PSLIST_READER_FIRST((H), T, F);			      \
		(V) != NULL;						      \
		(V) = PSLIST_READER_NEXT((V), T, F))

#endif	/* _SYS_PSLIST_H */

#include <stddef.h>
#include <string.h>

#include "pslist.h"

struct frotz {
	struct pslist_entry f_entry;
};

struct {
	kmutex_t lock;
	struct pslist_head list;
	pserialize_t psz;
} frobbotzim __cacheline_aligned;

void
frobbotzim_init(void)
{

	mutex_init(&frobbotzim.lock);
	PSLIST_INIT(&frobbotzim.list);
	psz = pserialize_create();
}

void
frotz_create(int key)
{
	struct frotz *f;

	f = ...;

	mutex_enter(&frobbotzim.lock);
	PSLIST_WRITER_INSERT_HEAD(&frobbotzim.list, f, f_entry);
	mutex_exit(&frobbotzim.lock);
}

int
frotz_lookup(int key)
{
	struct frotz *f;
	int result = -1;
	int s;

	s = pserialize_read_enter();
	PSLIST_READER_FOREACH(f, &frobbotzim.list, struct frotz, f_entry) {
		if (f->f_key == key) {
			result = f->f_fnord;
			break;
		}
	}
	pserialize_read_exit(s);

	return result;
}

void
frotz_destroy(int key)
{
	struct frotz *f;

	mutex_enter(&frobbotzim.lock);
	PSLIST_WRITER_FOREACH(f, &frobbotzim.list, struct frotz, f_entry) {
		if (f->f_key == key) {
			PSLIST_WRITER_REMOVE(f, f_entry);
			pserialize_perform(frobbotzim.psz);
			break;
		}
	}
	mutex_exit(&frobbotzim.lock);

	if (f != NULL)
		kmem_free(f, sizeof(*f));
}