From owner-svn-soc-all@FreeBSD.ORG Wed Aug 1 08:14:25 2012 Return-Path: Delivered-To: svn-soc-all@FreeBSD.org Received: from socsvn.FreeBSD.org (unknown [IPv6:2001:4f8:fff6::2f]) by hub.freebsd.org (Postfix) with SMTP id 455BF106566C for ; Wed, 1 Aug 2012 08:14:23 +0000 (UTC) (envelope-from gmiller@FreeBSD.org) Received: by socsvn.FreeBSD.org (sSMTP sendmail emulation); Wed, 01 Aug 2012 08:14:23 +0000 Date: Wed, 01 Aug 2012 08:14:23 +0000 From: gmiller@FreeBSD.org To: svn-soc-all@FreeBSD.org MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Message-Id: <20120801081423.455BF106566C@hub.freebsd.org> Cc: Subject: socsvn commit: r239983 - in soc2012/gmiller/locking-head: . tools/regression/lib/libwitness X-BeenThere: svn-soc-all@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: SVN commit messages for the entire Summer of Code repository List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 01 Aug 2012 08:14:25 -0000 Author: gmiller Date: Wed Aug 1 08:14:22 2012 New Revision: 239983 URL: http://svnweb.FreeBSD.org/socsvn/?view=rev&rev=239983 Log: r240028@FreeBSD-dev: root | 2012-07-24 12:09:57 -0500 Add additional tests to verify correct, optimal lock order graphs for the harder cases. Added: soc2012/gmiller/locking-head/tools/regression/lib/libwitness/graph.c soc2012/gmiller/locking-head/tools/regression/lib/libwitness/graph.t - copied unchanged from r239709, soc2012/gmiller/locking-head/tools/regression/lib/libwitness/setorder.t Modified: soc2012/gmiller/locking-head/ (props changed) soc2012/gmiller/locking-head/tools/regression/lib/libwitness/Makefile Modified: soc2012/gmiller/locking-head/tools/regression/lib/libwitness/Makefile ============================================================================== --- soc2012/gmiller/locking-head/tools/regression/lib/libwitness/Makefile Wed Aug 1 08:13:59 2012 (r239982) +++ soc2012/gmiller/locking-head/tools/regression/lib/libwitness/Makefile Wed Aug 1 08:14:22 2012 (r239983) @@ -1,7 +1,7 @@ # $FreeBSD$ -TESTS= lor-basic setorder bless setname -CFLAGS+= -g -Wall -Wextra -Werror -lwitness +TESTS= lor-basic setorder bless setname graph +CFLAGS+= -g -Wall -Wextra -Werror -lwitness -lpthread -static .PHONY: tests tests: ${TESTS} @@ -22,3 +22,6 @@ setname: setname.c check.c ${CC} -o setname setname.c check.c ${CFLAGS} + +graph: graph.c check.c + ${CC} -o graph graph.c check.c ${CFLAGS} Added: soc2012/gmiller/locking-head/tools/regression/lib/libwitness/graph.c ============================================================================== --- /dev/null 00:00:00 1970 (empty, because file is newly added) +++ soc2012/gmiller/locking-head/tools/regression/lib/libwitness/graph.c Wed Aug 1 08:14:22 2012 (r239983) @@ -0,0 +1,118 @@ +/*- + * Copyright (c) 2012 Greg Miller .. + * All rights reserved. + * + * 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 AUTHOR 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 AUTHOR 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. + * + */ + +#include +#include +#include + +#include "check.h" + +void +check_graph(pthread_mutex_t *lock_buffer, int lock_count) +{ + struct pthread_lockorder_np order; + int i; + + pthread_lockorder_begin_np(&order); + while (pthread_lockorder_next_np(&order)) { + i = (pthread_mutex_t *)order.lock - lock_buffer; + if (i >= 0 && i < lock_count) { + check((i < (lock_count - 1) && + (lock_buffer + i + 1) == order.child) || + (i == (lock_count - 1) && order.child == NULL)); + } + } + pthread_lockorder_end_np(&order); +} + +void +cycle_locks(pthread_mutex_t *lock_buffer, int *lock_set, int lock_set_size) +{ + int i = 0; + + while (i < lock_set_size) { + pthread_mutex_lock(&lock_buffer[lock_set[i++]]); + } + + while (--i >= 0) { + pthread_mutex_unlock(&lock_buffer[lock_set[i]]); + } +} + +void +graph_test(pthread_mutex_t *lock_buffer, int lock_count, int *lock_set, + int lock_set_size, int depth) +{ + if (depth == lock_count) { + cycle_locks(lock_buffer, lock_set, lock_set_size); + } else { + graph_test(lock_buffer, lock_count, lock_set, lock_set_size, + depth + 1); + + lock_set[lock_set_size++] = depth; + + graph_test(lock_buffer, lock_count, lock_set, lock_set_size, + depth + 1); + } +} + +void +all_tests(int lock_count) +{ + int i; + pthread_mutex_t *lock_buffer; + int *lock_set; + + pthread_lockorder_reset_np(); + + lock_buffer = malloc(sizeof(pthread_mutex_t) * lock_count); + lock_set = malloc(sizeof(int) * lock_count); + + for (i = 0; i < lock_count; i++) { + pthread_mutex_init(&lock_buffer[i], NULL); + } + + graph_test(lock_buffer, lock_count, lock_set, 0, 0); + check_graph(lock_buffer, lock_count); + + for (i = 0; i < lock_count; i++) { + pthread_mutex_destroy(&lock_buffer[i]); + } + + free(lock_set); + free(lock_buffer); +} + +int +main(void) +{ + all_tests(5); + + show_test_results(); + + return (0); +} Copied: soc2012/gmiller/locking-head/tools/regression/lib/libwitness/graph.t (from r239709, soc2012/gmiller/locking-head/tools/regression/lib/libwitness/setorder.t) ============================================================================== --- /dev/null 00:00:00 1970 (empty, because file is newly added) +++ soc2012/gmiller/locking-head/tools/regression/lib/libwitness/graph.t Wed Aug 1 08:14:22 2012 (r239983, copy of r239709, soc2012/gmiller/locking-head/tools/regression/lib/libwitness/setorder.t) @@ -0,0 +1,10 @@ +#!/bin/sh +# $FreeBSD$ + +cd `dirname $0` + +executable=`basename $0 .t` + +make $executable 2>&1 > /dev/null + +exec ./$executable