From owner-p4-projects@FreeBSD.ORG Wed May 21 20:11:09 2008 Return-Path: Delivered-To: p4-projects@freebsd.org Received: by hub.freebsd.org (Postfix, from userid 32767) id 48EA91065672; Wed, 21 May 2008 20:11:09 +0000 (UTC) Delivered-To: perforce@FreeBSD.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34]) by hub.freebsd.org (Postfix) with ESMTP id E4CA2106564A for ; Wed, 21 May 2008 20:11:08 +0000 (UTC) (envelope-from snagg@FreeBSD.org) Received: from repoman.freebsd.org (repoman.freebsd.org [IPv6:2001:4f8:fff6::29]) by mx1.freebsd.org (Postfix) with ESMTP id D39578FC19 for ; Wed, 21 May 2008 20:11:08 +0000 (UTC) (envelope-from snagg@FreeBSD.org) Received: from repoman.freebsd.org (localhost [127.0.0.1]) by repoman.freebsd.org (8.14.1/8.14.1) with ESMTP id m4LKB8Zu018450 for ; Wed, 21 May 2008 20:11:08 GMT (envelope-from snagg@FreeBSD.org) Received: (from perforce@localhost) by repoman.freebsd.org (8.14.1/8.14.1/Submit) id m4LKB8XH018448 for perforce@freebsd.org; Wed, 21 May 2008 20:11:08 GMT (envelope-from snagg@FreeBSD.org) Date: Wed, 21 May 2008 20:11:08 GMT Message-Id: <200805212011.m4LKB8XH018448@repoman.freebsd.org> X-Authentication-Warning: repoman.freebsd.org: perforce set sender to snagg@FreeBSD.org using -f From: Vincenzo Iozzo To: Perforce Change Reviews Cc: Subject: PERFORCE change 141985 for review X-BeenThere: p4-projects@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: p4 projects tree changes List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 21 May 2008 20:11:09 -0000 http://perforce.freebsd.org/chv.cgi?CH=141985 Change 141985 by snagg@snagg_macosx on 2008/05/21 20:10:25 Modify the sort and search function in order to use bsearch and qsort instead of bubblesort and my "home-made" binary search Affected files ... .. //depot/projects/soc2008/snagg-audit/sys/security/audit/audit_ioctl.h#11 edit .. //depot/projects/soc2008/snagg-audit/sys/security/audit/audit_pipe.c#13 edit Differences ... ==== //depot/projects/soc2008/snagg-audit/sys/security/audit/audit_ioctl.h#11 (text) ==== @@ -63,6 +63,7 @@ #define AUDITPIPE_PRESELECT_MODE_LOCAL 2 /* Local audit trail. */ #define AUDITPIPE_PRESELECT_MODE_EVENT 3 /* Events-pid based audit trail */ #define AUDITPIPE_PRESELECT_MODE_PID 4 /*Pid based audit trail*/ + /* * Ioctls to read and control the behavior of individual audit pipe devices. */ ==== //depot/projects/soc2008/snagg-audit/sys/security/audit/audit_pipe.c#13 (text) ==== @@ -230,61 +230,21 @@ /* * The event array is sorted in ascending order, needed for the binary search */ -static void audit_pipe_sort_preselect_event(struct audit_pipe_preselect_event *app_auevents, - int app_event_len) +static int +audit_pipe_compare_preselect_event(const void *a, const void *b) { - int sorted; - int i; - struct audit_pipe_preselect_event *entry; - - sorted = 0; - entry = NULL; - while(!sorted) { - sorted = 1; - for(i = 1; i < app_event_len; i++) { - if((app_auevents + i - 1)->app_event > (app_auevents + i)->app_event) { - *entry = *(app_auevents + i); - *(app_auevents + i) = *(app_auevents + i -1); - *(app_auevents + i -1) = *entry; - sorted = 0; - } - } - } -} + const struct audit_pipe_preselect_event *entrya = a; + const struct audit_pipe_preselect_event *entryb = b; + + if(entrya->app_event > entryb->app_event) + return 1; + else if (entrya->app_event < entryb->app_event) + return -1; + else + return 0; +} + -/* - * This is a basic implementation of the binary seach algorithm - */ -static struct audit_pipe_preselect_event - *audit_pipe_find_preselect_event(struct audit_pipe_preselect_event *app_auevents, - int app_event_len, int app_event, int app_flag) -{ - int bottom; - int top; - int curr; - - bottom = (app_auevents)->app_event; - top = (app_auevents + app_event_len -1)->app_event; - curr = 0; - - while(bottom <= top) { - curr = (bottom + top)/2; - if((app_auevents + curr)->app_event > app_event) - top = curr -1; - else if((app_auevents + curr)->app_event < app_event) - bottom = curr +1; - else { - if((app_auevents+curr)->app_flag == app_flag) - return (app_auevents + curr); - else if( app_flag == -1) - return (app_auevents + curr); - else - return (NULL); - } - } - - return (NULL); -} /* * Find an audit pipe preselection specification for an event and flag, if any. @@ -294,21 +254,32 @@ pid_t app_pid, int event_flag) { struct audit_pipe_preselect *app; + struct audit_pipe_preselect_event *event; + struct audit_pipe_preselect_event *ev_a; + + ev_a = malloc(sizeof(struct audit_pipe_preselect_event), M_AUDIT_PIPE_PRESELECT_EVENT, M_WAITOK); + ev_a->app_event = app_event; + ev_a->app_flag = event_flag; mtx_assert(&audit_pipe_mtx, MA_OWNED); TAILQ_FOREACH(app, &ap->ap_preselect_list, app_list) { if(app->app_pid == app_pid) { - if(app_event == -1) /* Just return the entry for a given pid*/ - return (app); - else { - if(audit_pipe_find_preselect_event(app->app_auevents, - app->app_event_len, app_event, event_flag) != NULL) - return (app); + if(app_event != -1) { /* Just skip if we are interested only in the pid*/ + event = bsearch(ev_a, (app->app_auevents), app->app_event_len, + sizeof(struct audit_pipe_preselect_event), + audit_pipe_compare_preselect_event); + if(event != NULL) { + if(event_flag != -1) + if (event->app_flag != event_flag) + app = NULL; + } else + app = NULL; } } } - return (NULL); + free(ev_a, M_AUDIT_PIPE_PRESELECT_EVENT); + return (app); } /* @@ -403,7 +374,7 @@ (app->app_auevents + i)->app_event = (events + i)->app_event; (app->app_auevents + i)->app_flag = (events + i)->app_flag; } - audit_pipe_sort_preselect_event(app->app_auevents, app->app_event_len); + qsort((app->app_auevents), app->app_event_len, sizeof(struct audit_pipe_preselect_event), audit_pipe_compare_preselect_event); } else { app = app_new; app_new = NULL; @@ -413,7 +384,7 @@ (app->app_auevents + i)->app_event = (events + i)->app_event; (app->app_auevents + i)->app_flag = (events + i)->app_flag; } - audit_pipe_sort_preselect_event(app->app_auevents, app->app_event_len); + qsort((app->app_auevents), app->app_event_len, sizeof(struct audit_pipe_preselect_event), audit_pipe_compare_preselect_event); TAILQ_INSERT_TAIL(&ap->ap_preselect_list, app, app_list); }