PERFORCE change 141808 for review

[Vincenzo Iozzo]

http://perforce.freebsd.org/chv.cgi?CH=141808

Change 141808 by snagg at 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);