Skip site navigation (1)Skip section navigation (2) 
Date:      Sun, 16 Feb 2003 20:56:44 -0800 (PST)
From:      Maksim Yevmenkin <m_evmenkin@yahoo.com>
To:        current@freebsd.org
Cc:        hackers@freebsd.org
Subject:   Need an expert's advise on WITNESS problem(?) (very long)
Message-ID:  <20030217045644.42272.qmail@web40305.mail.yahoo.com>
next in thread | raw e-mail | index | archive | help 
Dear Hackers,

I need an expert's advice on the small locking/WITNESS problem
(if this is a real problem of course). It basically boils down
to the following:

Consider three (3) MTX_DEF mutexes: A, B1 and B2. Mutex A has a
name "mutex_A" and type "type_A". Mutex B1 has a name "mutex_B1"
and mutex B2 has name "mutex_B2". Both mutex B1 and B2 have the
same type "type_B". Please note that mutexes B1 and B2 are
completely independent from each other. They just have the same
mutex type (B1 and B2 are used for fine grained locking).

Now consider the code that has two (2) paths: P1 and P2.

On the path P1 the code first acquires mutex A and then mutex
B1. Then the code releases mutex B1 and then mutex A.

On the path P2 the code first acquires mutex B2 and then mutex
A. Then the code releases mutex B2 and then mutex A.

So the code's flow looks something like this
 
        --->---\ /--->--- B1 --->--- Code path P1
                A
        ---<---/ \---<--- B2 ---<--- Code path P2

Now the problem (again if this is a problem) is that WITNESS
code builds relations between mutex types (or at least I think
it does). So when the code runs, WITNESS will build relations
between mutex types for the first path the code follows (lets
say P1). Later when the code follows the second path (in this
example P2), WITNESS will create "lock order reversal" message.

The questions are:

1) Is anything wrong with the such code and/or mutex use?
   Since mutexes B1 and B2 are completely independent, there
   is no deadlock danger, right? Please tell me if I'm wrong
   and missing something here.

2) Is there any way to resolve the problem? I'm prepared to
   change/re-design my code if needed.

3) Is WITNESS right in this case?

I have attached a small "spherical cow" that demonstrates
the example above. Just compile and load ng_cow.ko module
and then try

# ngctl msg cow: moo

Please advise.

thanks,
max

================ Makefile ============================
CFLAGS+=	-g
KMOD=		ng_cow
SRCS=		ng_cow.c
NOMAN=

.include <bsd.kmod.mk>

=============== ng_cow.c ==============================
#include <sys/param.h>
#include <sys/systm.h>
#include <sys/errno.h>
#include <sys/kernel.h>
#include <sys/lock.h>
#include <sys/malloc.h>
#include <sys/mbuf.h>
#include <sys/mutex.h>
#include <netgraph/ng_message.h>
#include <netgraph/netgraph.h>
#include <netgraph/ng_parse.h>

#define NG_COW_NODE_TYPE	"cow"
#define	NGM_COW_COOKIE		1018303300
#define	NGM_COW_MOO		1

#ifdef NG_SEPARATE_MALLOC
MALLOC_DEFINE(M_NETGRAPH_COW, "cow", "Netgraph spherical cow");
#else
#define M_NETGRAPH_COW M_NETGRAPH
#endif

static ng_constructor_t	ng_cow_constructor;
static ng_rcvmsg_t	ng_cow_rcvmsg;
static ng_shutdown_t	ng_cow_shutdown;
static ng_newhook_t	ng_cow_newhook;
static ng_connect_t	ng_cow_connect;
static ng_rcvdata_t	ng_cow_rcvdata;
static ng_disconnect_t	ng_cow_disconnect;
static int		ng_cow_modevent (module_t, int, void *);

static const struct ng_cmdlist	ng_cow_cmdlist[] = {
{
	NGM_COW_COOKIE,
	NGM_COW_MOO,
	"moo",
	NULL,
	NULL
},
{ 0, }
};

static struct ng_type	typestruct = {
	NG_ABI_VERSION,
	NG_COW_NODE_TYPE,	/* typename */
	ng_cow_modevent,	/* modevent */
	ng_cow_constructor,	/* constructor */
	ng_cow_rcvmsg,		/* control message */
	ng_cow_shutdown,	/* destructor */
	ng_cow_newhook,		/* new hook */
	NULL,			/* find hook */
	ng_cow_connect,		/* connect hook */
	ng_cow_rcvdata,		/* data */
	ng_cow_disconnect,	/* disconnect hook */
	ng_cow_cmdlist		/* node command list */
};
NETGRAPH_INIT(cow, &typestruct);
MODULE_VERSION(ng_cow, 1);

static node_p		the_node = NULL;
static struct mtx	a, b1, b2;

static int
ng_cow_modevent(module_t mod, int event, void *data)
{
	int	error = 0;

	switch (event) {
	case MOD_LOAD:
		error = ng_make_node_common(&typestruct, &the_node);
		if (error != 0)
			break;

		error = ng_name_node(the_node, NG_COW_NODE_TYPE);
		if (error != 0) {
			NG_NODE_UNREF(the_node);
			the_node = NULL;
			break;
		}

		mtx_init(&a,  "mutex_A",  "type_A", MTX_DEF);
		mtx_init(&b1, "mutex_B1", "type_B", MTX_DEF);
		mtx_init(&b2, "mutex_B2", "type_B", MTX_DEF);
		break;

	case MOD_UNLOAD:
		mtx_destroy(&a);
		mtx_destroy(&b1);
		mtx_destroy(&b2);
		break;

	default:
		error = EOPNOTSUPP;
		break;
	}

	return (error);
}

static int
ng_cow_constructor(node_p node)
{
	return (EINVAL);
}

static int
ng_cow_newhook(node_p node, hook_p hook, char const *name)
{
	return (EINVAL);
}

static int
ng_cow_connect(hook_p hook)
{
	return (EINVAL);
}

static int
ng_cow_disconnect(hook_p hook)
{
	return (0);
}

static int
ng_cow_shutdown(node_p node)
{
	NG_NODE_UNREF(node);
	the_node = NULL;
	return (0);
}

static int
ng_cow_rcvmsg(node_p node, item_p item, hook_p hook)
{
	struct ng_mesg	*msg = NULL;
	int		 error = 0;

	NGI_GET_MSG(item, msg);

	switch (msg->header.typecookie) {
	case NGM_COW_COOKIE:
		switch (msg->header.cmd) {
		case NGM_COW_MOO:
			/* PATH 1 */
			mtx_lock(&a);
			mtx_lock(&b1);
			mtx_unlock(&b1);
			mtx_unlock(&a);

			/* PATH 2 */
			mtx_lock(&b2);
			mtx_lock(&a);
			mtx_unlock(&a);
			mtx_unlock(&b2);
			break;

		default:
			error = EINVAL;
			break;
		}
		break;

	default:
		error = EINVAL;
		break;
	}

	NG_FREE_MSG(msg);

	return (error);
}

static int
ng_cow_rcvdata(hook_p hook, item_p item)
{
	NG_FREE_ITEM(item);
	return (0);
}



__________________________________________________
Do you Yahoo!?
Yahoo! Shopping - Send Flowers for Valentine's Day
http://shopping.yahoo.com

To Unsubscribe: send mail to majordomo@FreeBSD.org
with "unsubscribe freebsd-current" in the body of the message

Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20030217045644.42272.qmail>