r14956: change the notify search to be much more efficient by using a

per-depth bisection search. This makes the notify_trigger() call
log(N) which makes us scale well for large numbers of outstanding
notifies
(This used to be commit 16fd00925fdbf77e7a403ad501bf6ea429404c76)

4 files changed, 302 insertions, 85 deletions

diff --git a/source4/librpc/idl/notify.idl b/source4/librpc/idl/notify.idl
index 51c7cd1a01..cf544f3a68 100644
--- a/source4/librpc/idl/notify.idl
+++ b/source4/librpc/idl/notify.idl
@@ -19,12 +19,31 @@ interface notify
 		uint32 filter; /* filter to apply in this directory */
 		uint32 subdir_filter; /* filter to apply in child directories */
 		utf8string path;
+		uint32 path_len; /* saves some computation on search */
 		pointer private;
 	} notify_entry;
 
-	typedef [public] struct {
+	/*
+	  to allow for efficient search for matching entries, we
+	  divide them by the directory depth, with a separate array
+	  per depth. The entries within each depth are sorted by path,
+	  allowing for a bisection search.
+
+	  The max_mask and max_mask_subdir at each depth is the
+	  bitwise or of the filters and subdir filters for all entries
+	  at that depth. This allows a depth to be quickly skipped if
+	  no entries will match the target filter	  
+	*/
+	typedef struct {
+		uint32 max_mask;
+		uint32 max_mask_subdir;
 		uint32 num_entries;
 		notify_entry entries[num_entries];
+	} notify_depth;
+
+	typedef [public] struct {
+		uint32 num_depths;
+		notify_depth depth[num_depths];
 	} notify_array;
 
 	/* structure sent between servers in notify messages */
diff --git a/source4/ntvfs/common/notify.c b/source4/ntvfs/common/notify.c
index 318b114efa..0c264de88f 100644
--- a/source4/ntvfs/common/notify.c
+++ b/source4/ntvfs/common/notify.c
@@ -51,6 +51,7 @@ struct notify_list {
 	void *private;
 	void (*callback)(void *, const struct notify_event *);
 	void *sys_notify_handle;
+	int depth;
 };
 
 #define NOTIFY_KEY "notify array"
@@ -192,7 +193,14 @@ static NTSTATUS notify_save(struct notify_context *notify)
 	int ret;
 	TALLOC_CTX *tmp_ctx;
 
-	if (notify->array->num_entries == 0) {
+	/* if possible, remove some depth arrays */
+	while (notify->array->num_depths > 0 &&
+	       notify->array->depth[notify->array->num_depths-1].num_entries == 0) {
+		notify->array->num_depths--;
+	}
+
+	/* we might just be able to delete the record */
+	if (notify->array->num_depths == 0) {
 		ret = tdb_delete_bystring(notify->w->tdb, NOTIFY_KEY);
 		if (ret != 0) {
 			return NT_STATUS_INTERNAL_DB_CORRUPTION;
@@ -200,11 +208,6 @@ static NTSTATUS notify_save(struct notify_context *notify)
 		return NT_STATUS_OK;
 	}
 
-	if (notify->array->num_entries > 1) {
-		qsort(notify->array->entries, notify->array->num_entries, 
-		      sizeof(struct notify_entry), notify_compare);
-	}
-
 	tmp_ctx = talloc_new(notify);
 
 	status = ndr_push_struct_blob(&blob, tmp_ctx, notify->array, 
@@ -271,14 +274,53 @@ static void sys_notify_callback(struct sys_notify_context *ctx,
   add an entry to the notify array
 */
 static NTSTATUS notify_add_array(struct notify_context *notify, struct notify_entry *e,
-				 void *private)
+				 void *private, int depth)
 {
-	notify->array->entries[notify->array->num_entries] = *e;
-	notify->array->entries[notify->array->num_entries].private = private;
-	notify->array->entries[notify->array->num_entries].server = notify->server;
-	
-	notify->array->num_entries++;
-	
+	int i;
+	struct notify_depth *d;
+	struct notify_entry *ee;
+
+	/* possibly expand the depths array */
+	if (depth >= notify->array->num_depths) {
+		d = talloc_realloc(notify->array, notify->array->depth, 
+				   struct notify_depth, depth+1);
+		NT_STATUS_HAVE_NO_MEMORY(d);
+		for (i=notify->array->num_depths;i<=depth;i++) {
+			ZERO_STRUCT(d[i]);
+		}
+		notify->array->depth = d;
+		notify->array->num_depths = depth+1;
+	}
+	d = &notify->array->depth[depth];
+
+	/* expand the entries array */
+	ee = talloc_realloc(notify->array->depth, d->entries, struct notify_entry,
+			    d->num_entries+1);
+	NT_STATUS_HAVE_NO_MEMORY(ee);
+	d->entries = ee;
+
+	d->entries[d->num_entries] = *e;
+	d->entries[d->num_entries].private = private;
+	d->entries[d->num_entries].server = notify->server;
+	d->entries[d->num_entries].path_len = strlen(e->path);
+	d->num_entries++;
+
+	d->max_mask |= e->filter;
+	d->max_mask_subdir |= e->subdir_filter;
+
+	if (d->num_entries > 1) {
+		qsort(d->entries, d->num_entries, sizeof(d->entries[0]), notify_compare);
+	}
+
+	/* recalculate the maximum masks */
+	d->max_mask = 0;
+	d->max_mask_subdir = 0;
+
+	for (i=0;i<d->num_entries;i++) {
+		d->max_mask |= d->entries[i].filter;
+		d->max_mask_subdir |= d->entries[i].subdir_filter;
+	}
+
 	return notify_save(notify);
 }
 
@@ -295,6 +337,7 @@ NTSTATUS notify_add(struct notify_context *notify, struct notify_entry *e0,
 	char *tmp_path = NULL;
 	struct notify_list *listel;
 	size_t len;
+	int depth;
 
 	status = notify_lock(notify);
 	NT_STATUS_NOT_OK_RETURN(status);
@@ -304,15 +347,6 @@ NTSTATUS notify_add(struct notify_context *notify, struct notify_entry *e0,
 		goto done;
 	}
 
-	notify->array->entries = talloc_realloc(notify->array, notify->array->entries, 
-						struct notify_entry,
-						notify->array->num_entries+1);
-
-	if (notify->array->entries == NULL) {
-		status = NT_STATUS_NO_MEMORY;
-		goto done;
-	}
-
 	/* cope with /. on the end of the path */
 	len = strlen(e.path);
 	if (len > 1 && e.path[len-1] == '.' && e.path[len-2] == '/') {
@@ -324,6 +358,8 @@ NTSTATUS notify_add(struct notify_context *notify, struct notify_entry *e0,
 		e.path = tmp_path;
 	}
 
+	depth = count_chars(e.path, '/');
+
 	listel = talloc_zero(notify, struct notify_list);
 	if (listel == NULL) {
 		status = NT_STATUS_NO_MEMORY;
@@ -332,6 +368,7 @@ NTSTATUS notify_add(struct notify_context *notify, struct notify_entry *e0,
 
 	listel->private = private;
 	listel->callback = callback;
+	listel->depth = depth;
 	DLIST_ADD(notify->list, listel);
 
 	/* ignore failures from sys_notify */
@@ -353,7 +390,7 @@ NTSTATUS notify_add(struct notify_context *notify, struct notify_entry *e0,
 	   then we need to install it in the array used for the
 	   intra-samba notify handling */
 	if (e.filter != 0 || e.subdir_filter != 0) {
-		status = notify_add_array(notify, &e, private);
+		status = notify_add_array(notify, &e, private, depth);
 	}
 
 done:
@@ -370,7 +407,8 @@ NTSTATUS notify_remove(struct notify_context *notify, void *private)
 {
 	NTSTATUS status;
 	struct notify_list *listel;
-	int i;
+	int i, depth;
+	struct notify_depth *d;
 
 	for (listel=notify->list;listel;listel=listel->next) {
 		if (listel->private == private) {
@@ -382,6 +420,8 @@ NTSTATUS notify_remove(struct notify_context *notify, void *private)
 		return NT_STATUS_OBJECT_NAME_NOT_FOUND;
 	}
 
+	depth = listel->depth;
+
 	talloc_free(listel);
 
 	status = notify_lock(notify);
@@ -393,22 +433,25 @@ NTSTATUS notify_remove(struct notify_context *notify, void *private)
 		return status;
 	}
 
-	for (i=0;i<notify->array->num_entries;i++) {
-		if (notify->server == notify->array->entries[i].server && 
-		    private == notify->array->entries[i].private) {
+	/* we only have to search at the depth of this element */
+	d = &notify->array->depth[depth];
+
+	for (i=0;i<d->num_entries;i++) {
+		if (private == d->entries[i].private &&
+		    notify->server == d->entries[i].server) {
 			break;
 		}
 	}
-	if (i == notify->array->num_entries) {
+	if (i == d->num_entries) {
 		notify_unlock(notify);
 		return NT_STATUS_OBJECT_NAME_NOT_FOUND;
 	}
 
-	if (i < notify->array->num_entries-1) {
-		memmove(&notify->array->entries[i], &notify->array->entries[i+1], 
-			sizeof(notify->array->entries[i])*(notify->array->num_entries-(i+1)));
+	if (i < d->num_entries-1) {
+		memmove(&d->entries[i], &d->entries[i+1], 
+			sizeof(d->entries[i])*(d->num_entries-(i+1)));
 	}
-	notify->array->num_entries--;
+	d->num_entries--;
 
 	status = notify_save(notify);
 
@@ -423,7 +466,7 @@ NTSTATUS notify_remove(struct notify_context *notify, void *private)
 static NTSTATUS notify_remove_all(struct notify_context *notify)
 {
 	NTSTATUS status;
-	int i;
+	int i, depth, del_count=0;
 
 	if (notify->list == NULL) {
 		return NT_STATUS_OK;
@@ -438,19 +481,26 @@ static NTSTATUS notify_remove_all(struct notify_context *notify)
 		return status;
 	}
 
-	for (i=0;i<notify->array->num_entries;i++) {
-		if (notify->server == notify->array->entries[i].server) {
-			if (i < notify->array->num_entries-1) {
-				memmove(&notify->array->entries[i], &notify->array->entries[i+1], 
-					sizeof(notify->array->entries[i])*(notify->array->num_entries-(i+1)));
+	/* we have to search for all entries across all depths, looking for matches
+	   for our server id */
+	for (depth=0;depth<notify->array->num_depths;depth++) {
+		struct notify_depth *d = &notify->array->depth[depth];
+		for (i=0;i<d->num_entries;i++) {
+			if (notify->server == d->entries[i].server) {
+				if (i < d->num_entries-1) {
+					memmove(&d->entries[i], &d->entries[i+1], 
+						sizeof(d->entries[i])*(d->num_entries-(i+1)));
+				}
+				i--;
+				d->num_entries--;
+				del_count++;
 			}
-			i--;
-			notify->array->num_entries--;
 		}
 	}
 
-
-	status = notify_save(notify);
+	if (del_count > 0) {
+		status = notify_save(notify);
+	}
 
 	notify_unlock(notify);
 
@@ -487,61 +537,95 @@ static void notify_send(struct notify_context *notify, struct notify_entry *e,
 	talloc_free(tmp_ctx);
 }
 
-/*
-  see if a notify event matches
-*/
-static BOOL notify_match(struct notify_context *notify, struct notify_entry *e,
-			 const char *path, uint32_t filter)
-{
-	size_t len;
-	BOOL subdir;
-
-	if (!(filter & e->filter) && !(filter & e->subdir_filter)) {
-		return False;
-	}
-
-	len = strlen(e->path);
-
-	if (strncmp(path, e->path, len) != 0) {
-		return False;
-	}
-
-	if (path[len] != '/') {
-		return False;
-	}
-
-	/* the filter and subdir_filter are handled separately, allowing a backend
-	   to flexibly choose what it can handle */
-	subdir = (strchr(&path[len+1], '/') != NULL);
-
-	if (subdir) {
-		return (filter & e->subdir_filter) != 0;
-	}
-
-	return (filter & e->filter) != 0;
-}
-
 
 /*
   trigger a notify message for anyone waiting on a matching event
+
+  This function is called a lot, and needs to be very fast. The unusual data structure
+  and traversal is designed to be fast in the average case, even for large numbers of
+  notifies
 */
 void notify_trigger(struct notify_context *notify,
 		    uint32_t action, uint32_t filter, const char *path)
 {
 	NTSTATUS status;
-	int i;
+	int depth;
+	const char *p, *next_p;
 
 	status = notify_load(notify);
 	if (!NT_STATUS_IS_OK(status)) {
 		return;
 	}
 
-	/* TODO: this needs to be changed to a log(n) search */
-	for (i=0;i<notify->array->num_entries;i++) {
-		if (notify_match(notify, &notify->array->entries[i], path, filter)) {
-			notify_send(notify, &notify->array->entries[i], 
-				    path + strlen(notify->array->entries[i].path) + 1, 
-				    action);
+	/* loop along the given path, working with each directory depth separately */
+	for (depth=0,p=path;
+	     p && depth < notify->array->num_depths;
+	     p=next_p,depth++) {
+		int p_len = p - path;
+		int min_i, max_i, i;
+		struct notify_depth *d = &notify->array->depth[depth];
+		next_p = strchr(p+1, '/');
+
+		/* see if there are any entries at this depth */
+		if (d->num_entries == 0) continue;
+		
+		/* try to skip based on the maximum mask. If next_p is
+		 NULL then we know it will be a 'this directory'
+		 match, otherwise it must be a subdir match */
+		if (next_p != NULL) {
+			if (0 == (filter & d->max_mask_subdir)) {
+				continue;
+			}
+		} else {
+			if (0 == (filter & d->max_mask)) {
+				continue;
+			}
+		}
+
+		/* we know there is an entry here worth looking
+		 for. Use a bisection search to find the first entry
+		 with a matching path */
+		min_i = 0;
+		max_i = d->num_entries-1;
+
+		while (min_i < max_i) {
+			struct notify_entry *e;
+			i = (min_i+max_i)/2;
+			e = &d->entries[i];
+			int cmp = strncmp(path, e->path, p_len);
+			if (cmp == 0) {
+				if (p_len == e->path_len) {
+					max_i = i;
+				} else {
+					max_i = i-1;
+				}
+			} else if (cmp < 0) {
+				max_i = i-1;
+			} else {
+				min_i = i+1;
+			}
+		}
+
+		if (min_i != max_i) {
+			/* none match */
+			continue;
+		}
+
+		/* we now know that the entries start at min_i */
+		for (i=min_i;i<d->num_entries;i++) {
+			struct notify_entry *e = &d->entries[i];
+			if (p_len != e->path_len ||
+			    strncmp(path, e->path, p_len) != 0) break;
+			if (next_p != NULL) {
+				if (0 == (filter & e->subdir_filter)) {
+					continue;
+				}
+			} else {
+				if (0 == (filter & e->filter)) {
+					continue;
+				}
+			}
+			notify_send(notify, e, path + e->path_len + 1, action);
 		}
 	}
 }
diff --git a/source4/ntvfs/sysdep/sys_notify.c b/source4/ntvfs/sysdep/sys_notify.c
index 85831c80e9..13c8f4359a 100644
--- a/source4/ntvfs/sysdep/sys_notify.c
+++ b/source4/ntvfs/sysdep/sys_notify.c
@@ -42,7 +42,6 @@ struct sys_notify_context *sys_notify_init(int snum,
 {
 	struct sys_notify_context *ctx;
 	const char *bname;
-	struct sys_notify_backend *b;
 	int i;
 
 	if (num_backends == 0) {
diff --git a/source4/torture/raw/notify.c b/source4/torture/raw/notify.c
index 0e79a7ce07..8d024f983c 100644
--- a/source4/torture/raw/notify.c
+++ b/source4/torture/raw/notify.c
@@ -895,6 +895,120 @@ done:
 	return ret;
 }
 
+
+/* 
+   test multiple change notifies at different depths and with/without recursion
+*/
+static BOOL test_notify_tree(struct smbcli_state *cli, TALLOC_CTX *mem_ctx)
+{
+	BOOL ret = True;
+	struct smb_notify notify;
+	union smb_open io;
+	struct smbcli_request *req;
+	struct {
+		const char *path;
+		BOOL recursive;
+		uint32_t filter;
+		int expected;
+		int fnum;
+	} dirs[] = {
+		{BASEDIR "\\abc",               True, FILE_NOTIFY_CHANGE_NAME, 30 },
+		{BASEDIR "\\zqy",               True, FILE_NOTIFY_CHANGE_NAME, 8 },
+		{BASEDIR "\\atsy",              True, FILE_NOTIFY_CHANGE_NAME, 4 },
+		{BASEDIR "\\abc\\foo",          True,  FILE_NOTIFY_CHANGE_NAME, 2 },
+		{BASEDIR "\\abc\\blah",         True,  FILE_NOTIFY_CHANGE_NAME, 13 },
+		{BASEDIR "\\abc\\blah",         False, FILE_NOTIFY_CHANGE_NAME, 7 },
+		{BASEDIR "\\abc\\blah\\a",      True, FILE_NOTIFY_CHANGE_NAME, 2 },
+		{BASEDIR "\\abc\\blah\\b",      True, FILE_NOTIFY_CHANGE_NAME, 2 },
+		{BASEDIR "\\abc\\blah\\c",      True, FILE_NOTIFY_CHANGE_NAME, 2 },
+		{BASEDIR "\\abc\\fooblah",      True, FILE_NOTIFY_CHANGE_NAME, 2 },
+		{BASEDIR "\\zqy\\xx",           True, FILE_NOTIFY_CHANGE_NAME, 2 },
+		{BASEDIR "\\zqy\\yyy",          True, FILE_NOTIFY_CHANGE_NAME, 2 },
+		{BASEDIR "\\zqy\\..",           True, FILE_NOTIFY_CHANGE_NAME, 40 },
+		{BASEDIR,                       True, FILE_NOTIFY_CHANGE_NAME, 40 },
+		{BASEDIR,                       False,FILE_NOTIFY_CHANGE_NAME, 6 },
+		{BASEDIR "\\atsy",              False,FILE_NOTIFY_CHANGE_NAME, 4 },
+		{BASEDIR "\\abc",               True, FILE_NOTIFY_CHANGE_NAME, 24 },
+		{BASEDIR "\\abc",               False,FILE_NOTIFY_CHANGE_FILE_NAME, 0 },
+		{BASEDIR "\\abc",               True, FILE_NOTIFY_CHANGE_FILE_NAME, 0 },
+		{BASEDIR "\\abc",               True, FILE_NOTIFY_CHANGE_NAME, 24 },
+	};
+	int i;
+	NTSTATUS status;
+
+	printf("TESTING CHANGE NOTIFY FOR DIFFERENT DEPTHS\n");
+
+	io.generic.level = RAW_OPEN_NTCREATEX;
+	io.ntcreatex.in.root_fid = 0;
+	io.ntcreatex.in.flags = 0;
+	io.ntcreatex.in.access_mask = SEC_FILE_ALL;
+	io.ntcreatex.in.create_options = NTCREATEX_OPTIONS_DIRECTORY;
+	io.ntcreatex.in.file_attr = FILE_ATTRIBUTE_NORMAL;
+	io.ntcreatex.in.share_access = NTCREATEX_SHARE_ACCESS_READ | NTCREATEX_SHARE_ACCESS_WRITE;
+	io.ntcreatex.in.alloc_size = 0;
+	io.ntcreatex.in.open_disposition = NTCREATEX_DISP_OPEN_IF;
+	io.ntcreatex.in.impersonation = NTCREATEX_IMPERSONATION_ANONYMOUS;
+	io.ntcreatex.in.security_flags = 0;
+
+	notify.in.buffer_size = 20000;
+
+	/*
+	  setup the directory tree, and the notify buffer on each directory
+	*/
+	for (i=0;i<ARRAY_SIZE(dirs);i++) {
+		io.ntcreatex.in.fname = dirs[i].path;
+		status = smb_raw_open(cli->tree, mem_ctx, &io);
+		CHECK_STATUS(status, NT_STATUS_OK);
+		dirs[i].fnum = io.ntcreatex.out.file.fnum;
+
+		notify.in.completion_filter = dirs[i].filter;
+		notify.in.file.fnum = dirs[i].fnum;
+		notify.in.recursive = dirs[i].recursive;
+		req = smb_raw_changenotify_send(cli->tree, &notify);
+		smb_raw_ntcancel(req);
+		status = smb_raw_changenotify_recv(req, mem_ctx, &notify);
+		CHECK_STATUS(status, NT_STATUS_CANCELLED);
+	}
+
+	/* trigger 2 events in each dir */
+	for (i=0;i<ARRAY_SIZE(dirs);i++) {
+		char *path = talloc_asprintf(mem_ctx, "%s\\test.dir", dirs[i].path);
+		smbcli_mkdir(cli->tree, path);
+		smbcli_rmdir(cli->tree, path);
+		talloc_free(path);
+	}
+
+	/* give a bit of time for all the events to propogate */
+	sleep(2);
+
+	/* count events that have happened in each dir */
+	for (i=0;i<ARRAY_SIZE(dirs);i++) {
+		notify.in.file.fnum = dirs[i].fnum;
+		req = smb_raw_changenotify_send(cli->tree, &notify);
+		smb_raw_ntcancel(req);
+		notify.out.num_changes = 0;
+		status = smb_raw_changenotify_recv(req, mem_ctx, &notify);
+		if (notify.out.num_changes != dirs[i].expected) {
+			printf("ERROR: i=%d expected %d got %d for '%s'\n",
+			       i, dirs[i].expected, notify.out.num_changes,
+			       dirs[i].path);
+			ret = False;
+		}
+	}
+
+	/*
+	  run from the back, closing and deleting
+	*/
+	for (i=ARRAY_SIZE(dirs)-1;i>=0;i--) {
+		smbcli_close(cli->tree, dirs[i].fnum);
+		smbcli_rmdir(cli->tree, dirs[i].path);
+	}
+
+done:
+	smb_raw_exit(cli->session);
+	return ret;
+}
+
 /* 
    basic testing of change notify
 */
@@ -922,6 +1036,7 @@ BOOL torture_raw_notify(struct torture_context *torture)
 	ret &= test_notify_exit(mem_ctx);
 	ret &= test_notify_ulogoff(mem_ctx);
 	ret &= test_notify_double(cli, mem_ctx);
+	ret &= test_notify_tree(cli, mem_ctx);
 
 	smb_raw_exit(cli->session);
 	smbcli_deltree(cli->tree, BASEDIR);