From owner-p4-projects@FreeBSD.ORG Sun May 18 14:13:52 2008 Return-Path: Delivered-To: p4-projects@freebsd.org Received: by hub.freebsd.org (Postfix, from userid 32767) id 937F41065677; Sun, 18 May 2008 14:13:52 +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 55D031065672 for ; Sun, 18 May 2008 14:13:52 +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 46AAD8FC16 for ; Sun, 18 May 2008 14:13:52 +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 m4IEDq4K028998 for ; Sun, 18 May 2008 14:13:52 GMT (envelope-from snagg@FreeBSD.org) Received: (from perforce@localhost) by repoman.freebsd.org (8.14.1/8.14.1/Submit) id m4IEDq1K028996 for perforce@freebsd.org; Sun, 18 May 2008 14:13:52 GMT (envelope-from snagg@FreeBSD.org) Date: Sun, 18 May 2008 14:13:52 GMT Message-Id: <200805181413.m4IEDq1K028996@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 141808 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: Sun, 18 May 2008 14:13:52 -0000 http://perforce.freebsd.org/chv.cgi?CH=141808 Change 141808 by snagg@snagg_macosx on 2008/05/18 14:13:45 Doing some style revisions. Added the sorting algorithm for the event array. Added the binary search to improve speed for event searches. Affected files ... .. //depot/projects/soc2008/snagg-audit/sys/security/audit/audit_pipe.c#11 edit Differences ... ==== //depot/projects/soc2008/snagg-audit/sys/security/audit/audit_pipe.c#11 (text) ==== @@ -228,13 +228,72 @@ } /* + * 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) +{ + 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; + } + } + } +} + +/* + * 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. */ static struct audit_pipe_preselect * -audit_pipe_preselect_find_event(struct audit_pipe *ap, int app_event, pid_t app_pid, int event_flag) +audit_pipe_preselect_find_event(struct audit_pipe *ap, int app_event, + pid_t app_pid, int event_flag) { struct audit_pipe_preselect *app; - int i; mtx_assert(&audit_pipe_mtx, MA_OWNED); @@ -242,16 +301,13 @@ if(app->app_pid == app_pid) { if(app_event == -1) return (app); - for(i = 0; i < app->app_event_len; i++) - if((app->app_auevents + i)->app_event == app_event) { - if(event_flag == -1) + else { + if(audit_pipe_find_preselect_event(app->app_auevents, + app->app_event_len, app_event, event_flag) != NULL) return (app); - else if ((app->app_auevents + i)->app_flag == event_flag) - return (app); - } + } } } - return (NULL); } @@ -319,7 +375,8 @@ * otherwise, update the current entry. */ static void -audit_pipe_preselect_set_events(struct audit_pipe *ap, pid_t app_pid, struct audit_pipe_preselect_event *events, int num) +audit_pipe_preselect_set_events(struct audit_pipe *ap, pid_t app_pid, + struct audit_pipe_preselect_event *events, int num) { struct audit_pipe_preselect *app, *app_new; int i; @@ -330,7 +387,9 @@ * exist, and allocate. We will free it if it is unneeded. */ app_new = malloc(sizeof(*app_new), M_AUDIT_PIPE_PRESELECT, M_WAITOK); - app_new->app_auevents= malloc(sizeof(struct audit_pipe_preselect_event) * AUDIT_NEVENTS, M_AUDIT_PIPE_PRESELECT_EVENT, M_WAITOK); + app_new->app_auevents= malloc(sizeof(struct audit_pipe_preselect_event) + * AUDIT_NEVENTS, M_AUDIT_PIPE_PRESELECT_EVENT, + M_WAITOK); mtx_lock(&audit_pipe_mtx); /* @@ -343,7 +402,8 @@ for (i = 0; i < num; i++) { (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); } else { app = app_new; app_new = NULL; @@ -352,7 +412,8 @@ for (i = 0; i < num; i++) { (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); TAILQ_INSERT_TAIL(&ap->ap_preselect_list, app, app_list); } @@ -397,7 +458,8 @@ */ /* static int -audit_pipe_preselect_delete_event(struct audit_pipe *ap, int app_event, pid_t pid, int app_flag) +audit_pipe_preselect_delete_event(struct audit_pipe *ap, int app_event, pid_t pid, + int app_flag) { struct audit_pipe_preselect *app; int i; @@ -406,7 +468,8 @@ app = audit_pipe_preselect_find_event(ap, app_event, pid, -1); if (app != NULL) { for( i = 0; i < app->app_event_len; i++) { - if((app->app_auevents + i)->app_event == app_event && (app->app_auevents + i)->app_flag == app_flag) { + if((app->app_auevents + i)->app_event == app_event && + (app->app_auevents + i)->app_flag == app_flag) { free((app->app_auevents + i), M_AUDIT_PIPE_PRESELECT_EVENT); break; } @@ -439,7 +502,7 @@ free((app->app_auevents + i), M_AUDIT_PIPE_PRESELECT_EVENT); free(app, M_AUDIT_PIPE_PRESELECT); return (0); - }else + } else mtx_unlock(&audit_pipe_mtx); return (ENOENT); @@ -1018,7 +1081,9 @@ case AUDITPIPE_SET_PRESELECT_EVENTS: aip = (struct auditpipe_ioctl_preselect *)data; - audit_pipe_preselect_set_events(ap, aip->app_pid, (struct audit_pipe_preselect_event *)taip->app_auevents, aip->app_event_len); + audit_pipe_preselect_set_events(ap, aip->app_pid, + (struct audit_pipe_preselect_event *)aip->app_auevents, + aip->app_event_len); error = 0; break; @@ -1060,7 +1125,7 @@ switch (mode) { case AUDITPIPE_PRESELECT_MODE_TRAIL: case AUDITPIPE_PRESELECT_MODE_LOCAL: - case AUDITPIPE_PRESELECT_MODE_SYSCALL: + case AUDITPIPE_PRESELECT_MODE_EVENT: mtx_lock(&audit_pipe_mtx); ap->ap_preselect_mode = mode; mtx_unlock(&audit_pipe_mtx);