dirsync review

[tridge at samba.org]

Hi Matthieu,

Andrew and I looked over the dirsync code today. Impressive work!

The comments below are in two parts. One is "micro" comments on the
individual lines of code. The other is higher level comments on the
broad approach taken.

Here are the 'micro' comments:

 - the strncmp() in rootdse.c for LDB_CONTROL_DIRSYNC_OID should be a
   strcmp(), otherwise it will match other OIDs (OIDs can be different
   lengths)

 - the DSDB_CONTROL_DIRSYNC_RELAX_CHECK_OID doesn't seem to be ever
   set. It's used in acl_read, but not set anywhere. Did you miss a
   patch?

 - DSDB_CONTROL_DIRSYNC_RELAX_CHECK_OID might be better implemented as
   a handle flag, like LDB_HANDLE_FLAG_UNTRUSTED. The control works,
   but adding/checking controls is a lot more expensive than flags.

 - it might be better to call dsdb_module_search_ex() something like
   dsdb_module_search_tree(). Otherwise next time we add a new feature
   we'll end up with ex2 and so on :-)

 - a talloc_free(tmp_ctx) is missing when ldb_parse_tree() fails in
   dsdb_module_search() 

 - in dirsync_ldb_search() the ldb_dn_is_special() check should be
   earlier, before dsc is allocated

 - same with the ldb_request_get_control() call

 - the check for it being critical can come before the
   talloc_get_type() call

 - you need to check if the dirsync_ctl is NULL after the
   talloc_get_type() (as users could supply the control with no data)

 - its best to make attribute lists the same scope as the call, so
   they are easier to find in the code, so acl_attrs[] should be
   declared inside the LDAP_DIRSYNC_OBJECT_SECURITY if() check

 - you don't need to check for acl_res->count != 1 after a
   dsdb_module_search_dn(). When searching on one dn, you either get 1
   answer, or an error (its checked for inside the search)

 - its nice to keep the talloc hierarchy when creating arrays, as it
   makes debugging easier. so attrs[0] = talloc_asprintf(dsc, "*")
   should be attrs[0] = talloc_asprintf(attrs, "*") (there are a few
   other places like this)

 - please use ldb_operr() instead of "return
   LDB_ERR_OPERATIONS_ERROR", as that sets a error message with file
   and line, so we can find the error (there are quite a few of these
   in dirsync.c)

 - Similarly, use ldb_error() instead of just returning a LDB_ERR_* in
   modules, unless you know an error string is already set. It helps a
   lot to get the ldap protocol to send back an error string saying
   exactly what went wrong

 - the code checks for failures of functions that do allocation in
   some places but not others (eg. calls to ldb_attr_list_copy_add())

 - in this code:

		attrs[0] = talloc_asprintf(dsc, "*");
		attrs[1] = "parentGUID";

   why use a allocation for the first one, and a constant string for
   the 2nd one? If it is needed for some reason, then I think a
   comment would be useful :-)

 - the function dirsync_ldb_search() adds a lot of controls. Do you
   know if we should fail if the user already has specified one of
   these? Should we do this for example:

	ret = ldb_request_add_control(req, LDB_CONTROL_SHOW_RECYCLED_OID, false, NULL);
	if (ret != LDB_SUCCESS && ret != LDB_ERR_ATTRIBUTE_OR_VALUE_EXISTS) {
		return ret;
	}


 - its probably worth hanging most things off dsc instead of req, if
   its related to the dirsync control, eg. the ldb_parse_tree in the
   USN check. That will make it a bit easier to track down leaks if
   they happen

 - the code that creates the ldb_parse_tree structure would probably
   be much clearer using talloc_asprintf() of an expression, and then
   using that expression. Creating a ldb_parse_tree() manually does
   work, but its very hard to read the code. For example, do this:

     expression = talloc_asprintf(dsc, "(&%s(uSNChanged>=%llu))", 
                                  ldb_filter_from_tree(dsc, tree),
				  dsc->fromreqUSN + 1);

   I know its less efficient than the code you have, but it is much
   easier to read, and I don't think this function is speed critical

 - saved_controls is never used, so just pass NULL to
   ldb_save_controls() (we never use the saved controls in Samba, so
   we should probably have a ldb_remove_control() function to make it
   clearer)

 - in the LDB_REPLY_REFERRAL handling, I think it would be worth
   checking that the 8 chars that are being skipped really are what
   you expect (ie. a ldap://)

 - why the strange cast in this code:

		val = (struct ldb_val*)&res2->msgs[0]->elements[0].values[0].data;

   perhaps that should be just:

		val = &res2->msgs[0]->elements[0].values[0];

 - why steal the val here?

		talloc_steal(res->msgs[0]->elements, val);

 - I think this code should just use ldb_oom():

		control = talloc_zero(ares->controls, struct ldb_dirsync_control);
		if (control == NULL) {
			return ldb_module_done(dsc->req, NULL, NULL, LDB_ERR_OPERATIONS_ERROR);
		}
   (there are a few others like this)

 - when allocating things like struct drsuapi_DsReplicaCursor, its
   best to use talloc_zero() not talloc(). I think the code may have
   left some fields unset.

 - this looks very strange:

		cookie->blob.guid1 = *(talloc_steal(cookie, dsc->our_invocation_id));

   I think you just want this:

		cookie->blob.guid1 = *dsc->our_invocation_id;

 - use ldb_error() when returning errors for things like
   ndr_push_struct_blob() so we have a record of what the error is in
   the ldap response packet

 - why use strncmp() here:

		if (strncmp(msg->elements[i].name, "uSNChanged", sizeof("uSNChanged") -1) == 0) {

   I think strcmp() is correct. Otherwise you'll match things starting
   with uSNChanged. You only really need strncmp() when you are
   comparing with a blob that has a specified length, such as when it
   is a ldb_val, and even then just doing the strncmp() isn't enough,
   you'd have to check for the termination character.

   There are several cases like this in the code, please check all
   strncmp() calls in dirsync.c - I think they should all be strcmp()
   or ldb_attr_cmp(). I think most of them should be ldb_attr_cmp() as
   they are not case sensitive

   There are also quite a few cases where the code uses strcmp() which
   I suspect should be ldb_attr_cmp(), for example looking for
   "instanceType"


 - what is this for:

			val = strtoull((const char *)msg->elements[i].values[0].data, NULL, 0);

   I don't think val is used afterwards?

 - this is another cast and steal that I don't think is right:

			replMetaData = (struct ldb_val *)talloc_steal(dsc, &msg->elements[i].values[0].data);

   (one is a structure, the other an element of the structure, this
   could well cause a crash on some systems. The code relies on
   structure order and structure packing, which is dangerous)

   if you need the steal, then I think what you want is this:

      	  	struct ldb_val replMetaData = data_blob_null;
		if (some_condition) {
		        replMetaData = msg->elements[i].values[0];
			talloc_steal(dsc, replMetaData.data);
		}
		/* later on .... */
		if (replMetaData.data != NULL) {
		   /* use it .... */
		}

  - the O() analysis may be a bit optimistic, as
    ldb_msg_remove_element() costs O(n), as it does a memmove(), so I
    think its O(n^3). It may be better to first create a new array
    equal in size to the old array, then populate it with ones that
    match the filter. 

  - the check

      tmp = strstr(txt, ",CN=Deleted Objects,");

    doesn't look right. That string could appear anywhere in a DN, and
    not have a special meaning.

    Perhaps its better to check for the isDeleted attribute?

  - this code looks a bit strange:

		tmpval.data = NULL;
		tmpval.length = 0;
		/* code cut out ..... */
		msg->dn = ldb_dn_from_ldb_val(msg, ldb, &tmpval);

   do you just want the empty DN here? I think 
     ldb_dn_new(msg, ldb, "") 
   would be clearer if that is what's wanted

  - in this code:

		for (i = msg->num_elements - 1; i >= 0; i--) {
			attr = dsdb_attribute_by_lDAPDisplayName(dsc->schema,
					msg->elements[i].name);

    I can't see where attr ends up being used. Is it needed?

 - in that same loop, it looks like what is being done is to remove
   all elements if they aren't objectGUID. Perhaps just do this:

    if (ldb_msg_find_element(msg, "objectGUID") != NULL) {
       guidfound = true;
    }

 - the code to cope with guidfound==false seems strange. Under what
   circumstances would we not be able to get the objectGUID if we ask
   for it? Parsing the deleted objected DEL: string seems very strange
   to me!


Now for the 'broad' comments on the basic approach. 

One of the things that concerns me is the efficiency of the approach
in the code. Let's say that a directory has 100k records, and someone
uses dirsync to pull them all, 100 elements at a time. If I have
understood the protocol correctly, then I think that means 1000 calls
will be made, the first without a cookie and the rest with a cookie
returned by the previous call.

I think that the dirsync.c code as currently implemented will end up
doing an unindexed search over all 100k elements in the database 1000
times. So we are about 1000 times less efficient than we should be.

An alternative approach is what the getncchanges.c code does, which is
to load a list of matching objectGUIDs on the first step of the
search, which we save in the guids[] array of
drsuapi_getncchanges_state. Then subsequent calls return records from
this list of GUIDs, by fetching those records one at a time. This
means we only do one non-indexed search for a complete directory
return.

I think this same strategy could be used in dirsync. You'd keep a
persistent set of dirsync state structures in the dirsync module
private data. When a dirsync search comes in, then if it doesn't have
a cookie then create a new one, and remember it. For real efficiency,
use an idr tree.

If the request did have a cookie then look it up in the idr tree, and
get back the state structure for that request.

The state structure would have an array of GUIDs that match the simple
search uSNChanged>=N from the first search. That is a fairly compact
representation of all the records that could be returned.

Then the code would just walk this list, fetch each record one at a
time, and adding it to the returned list if it matches. You'd have
just one non-base search per set of dirsync calls.

It might also be worth having a timer that deletes stale dirsync
cookies, in case a caller asks for one then doesn't come back
again. Does the spec talk about the state timing out?

Do you think that approach would work?

Cheers, Tridge