Add a comment describing the sorted subkeys
[ira/wip.git] / source3 / registry / reg_backend_db.c
index e0be8f39750510e472e5fc6ab9bd524d3b07f60e..344bc4124d360797db07d06e4323c3e03fb0811e 100644 (file)
@@ -27,6 +27,9 @@
 static struct db_context *regdb = NULL;
 static int regdb_refcount;
 
+static bool regdb_key_exists(const char *key);
+static bool regdb_key_is_base_key(const char *key);
+
 /* List the deepest path into the registry.  All part components will be created.*/
 
 /* If you want to have a part of the path controlled by the tdb and part by
@@ -91,9 +94,9 @@ static struct builtin_regkey_value builtin_registry_values[] = {
  * Initialize a key in the registry:
  * create each component key of the specified path.
  */
-static bool init_registry_key_internal(const char *add_path)
+static WERROR init_registry_key_internal(const char *add_path)
 {
-       bool ret = false;
+       WERROR werr;
        TALLOC_CTX *frame = talloc_stackframe();
        char *path = NULL;
        char *base = NULL;
@@ -108,6 +111,7 @@ static bool init_registry_key_internal(const char *add_path)
        path = talloc_strdup(frame, add_path);
        base = talloc_strdup(frame, "");
        if (!path || !base) {
+               werr = WERR_NOMEM;
                goto fail;
        }
        p = path;
@@ -119,11 +123,13 @@ static bool init_registry_key_internal(const char *add_path)
                if (*base) {
                        base = talloc_asprintf(frame, "%s\\", base);
                        if (!base) {
+                               werr = WERR_NOMEM;
                                goto fail;
                        }
                }
                base = talloc_asprintf_append(base, "%s", keyname);
                if (!base) {
+                       werr = WERR_NOMEM;
                        goto fail;
                }
 
@@ -131,11 +137,13 @@ static bool init_registry_key_internal(const char *add_path)
 
                subkeyname = talloc_strdup(frame, "");
                if (!subkeyname) {
+                       werr = WERR_NOMEM;
                        goto fail;
                }
                if (*p) {
                        remaining = talloc_strdup(frame, p);
                        if (!remaining) {
+                               werr = WERR_NOMEM;
                                goto fail;
                        }
                        p2 = remaining;
@@ -145,6 +153,7 @@ static bool init_registry_key_internal(const char *add_path)
                        {
                                subkeyname = talloc_strdup(frame,p2);
                                if (!subkeyname) {
+                                       werr = WERR_NOMEM;
                                        goto fail;
                                }
                        }
@@ -160,22 +169,28 @@ static bool init_registry_key_internal(const char *add_path)
 
                if (!(subkeys = TALLOC_ZERO_P(frame, REGSUBKEY_CTR))) {
                        DEBUG(0,("talloc() failure!\n"));
+                       werr = WERR_NOMEM;
                        goto fail;
                }
 
                regdb_fetch_keys(base, subkeys);
                if (*subkeyname) {
-                       regsubkey_ctr_addkey( subkeys, subkeyname);
+                       werr = regsubkey_ctr_addkey(subkeys, subkeyname);
+                       if (!W_ERROR_IS_OK(werr)) {
+                               goto fail;
+                       }
                }
                if (!regdb_store_keys( base, subkeys)) {
+                       werr = WERR_CAN_NOT_COMPLETE;
                        goto fail;
                }
        }
 
-       ret = true;
+       werr = WERR_OK;
+
 fail:
        TALLOC_FREE(frame);
-       return ret;
+       return werr;
 }
 
 /**
@@ -183,43 +198,84 @@ fail:
  * create each component key of the specified path,
  * wrapped in one db transaction.
  */
-bool init_registry_key(const char *add_path)
+WERROR init_registry_key(const char *add_path)
 {
-       if (regdb->transaction_start(regdb) == -1) {
+       WERROR werr;
+
+       if (regdb_key_exists(add_path)) {
+               return WERR_OK;
+       }
+
+       if (regdb->transaction_start(regdb) != 0) {
                DEBUG(0, ("init_registry_key: transaction_start failed\n"));
-               return false;
+               return WERR_REG_IO_FAILURE;
        }
 
-       if (!init_registry_key_internal(add_path)) {
+       werr = init_registry_key_internal(add_path);
+       if (!W_ERROR_IS_OK(werr)) {
                goto fail;
        }
 
-       if (regdb->transaction_commit(regdb) == -1) {
+       if (regdb->transaction_commit(regdb) != 0) {
                DEBUG(0, ("init_registry_key: Could not commit transaction\n"));
-               return false;
+               return WERR_REG_IO_FAILURE;
        }
 
-       return true;
+       return WERR_OK;
 
 fail:
-       if (regdb->transaction_cancel(regdb) == -1) {
+       if (regdb->transaction_cancel(regdb) != 0) {
                smb_panic("init_registry_key: transaction_cancel failed\n");
        }
 
-       return false;
+       return werr;
 }
 
 /***********************************************************************
  Open the registry data in the tdb
  ***********************************************************************/
 
-bool init_registry_data(void)
+WERROR init_registry_data(void)
 {
-       TALLOC_CTX *frame = NULL;
+       WERROR werr;
+       TALLOC_CTX *frame = talloc_stackframe();
        REGVAL_CTR *values;
        int i;
        UNISTR2 data;
 
+       /*
+        * First, check for the existence of the needed keys and values.
+        * If all do already exist, we can save the writes.
+        */
+       for (i=0; builtin_registry_paths[i] != NULL; i++) {
+               if (!regdb_key_exists(builtin_registry_paths[i])) {
+                       goto do_init;
+               }
+       }
+
+       for (i=0; builtin_registry_values[i].path != NULL; i++) {
+               values = TALLOC_ZERO_P(frame, REGVAL_CTR);
+               if (values == NULL) {
+                       werr = WERR_NOMEM;
+                       goto done;
+               }
+
+               regdb_fetch_values(builtin_registry_values[i].path, values);
+               if (!regval_ctr_key_exists(values,
+                                       builtin_registry_values[i].valuename))
+               {
+                       TALLOC_FREE(values);
+                       goto do_init;
+               }
+
+               TALLOC_FREE(values);
+       }
+
+       werr = WERR_OK;
+       goto done;
+
+do_init:
+
        /*
         * There are potentially quite a few store operations which are all
         * indiviually wrapped in tdb transactions. Wrapping them in a single
@@ -228,28 +284,32 @@ bool init_registry_data(void)
         * transaction behaviour.
         */
 
-       if (regdb->transaction_start(regdb) == -1) {
+       if (regdb->transaction_start(regdb) != 0) {
                DEBUG(0, ("init_registry_data: tdb_transaction_start "
                          "failed\n"));
-               return false;
+               werr = WERR_REG_IO_FAILURE;
+               goto done;
        }
 
        /* loop over all of the predefined paths and add each component */
 
        for (i=0; builtin_registry_paths[i] != NULL; i++) {
-               if (!init_registry_key_internal(builtin_registry_paths[i])) {
+               if (regdb_key_exists(builtin_registry_paths[i])) {
+                       continue;
+               }
+               werr = init_registry_key_internal(builtin_registry_paths[i]);
+               if (!W_ERROR_IS_OK(werr)) {
                        goto fail;
                }
        }
 
        /* loop over all of the predefined values and add each component */
 
-       frame = talloc_stackframe();
-
        for (i=0; builtin_registry_values[i].path != NULL; i++) {
 
                values = TALLOC_ZERO_P(frame, REGVAL_CTR);
                if (values == NULL) {
+                       werr = WERR_NOMEM;
                        goto fail;
                }
 
@@ -292,53 +352,54 @@ bool init_registry_data(void)
                TALLOC_FREE(values);
        }
 
-       TALLOC_FREE(frame);
-
-       if (regdb->transaction_commit(regdb) == -1) {
+       if (regdb->transaction_commit(regdb) != 0) {
                DEBUG(0, ("init_registry_data: Could not commit "
                          "transaction\n"));
-               return false;
+               werr = WERR_REG_IO_FAILURE;
+       } else {
+               werr = WERR_OK;
        }
 
-       return true;
+       goto done;
 
- fail:
-
-       TALLOC_FREE(frame);
-
-       if (regdb->transaction_cancel(regdb) == -1) {
+fail:
+       if (regdb->transaction_cancel(regdb) != 0) {
                smb_panic("init_registry_data: tdb_transaction_cancel "
                          "failed\n");
        }
 
-       return false;
+done:
+       TALLOC_FREE(frame);
+       return werr;
 }
 
 /***********************************************************************
  Open the registry database
  ***********************************************************************/
  
-bool regdb_init(void)
+WERROR regdb_init(void)
 {
        const char *vstring = "INFO/version";
        uint32 vers_id;
+       WERROR werr;
 
        if (regdb) {
                DEBUG(10, ("regdb_init: incrementing refcount (%d)\n",
                          regdb_refcount));
                regdb_refcount++;
-               return true;
+               return WERR_OK;
        }
 
-       regdb = db_open(NULL, state_path("registry.tdb"), 0, REG_TDB_FLAGS,
-                       O_RDWR, 0600);
+       regdb = db_open(NULL, state_path("registry.tdb"), 0,
+                             REG_TDB_FLAGS, O_RDWR, 0600);
        if (!regdb) {
                regdb = db_open(NULL, state_path("registry.tdb"), 0,
-                               REG_TDB_FLAGS, O_RDWR|O_CREAT, 0600);
+                                     REG_TDB_FLAGS, O_RDWR|O_CREAT, 0600);
                if (!regdb) {
-                       DEBUG(0,("regdb_init: Failed to open registry %s (%s)\n",
+                       werr = ntstatus_to_werror(map_nt_error_from_unix(errno));
+                       DEBUG(1,("regdb_init: Failed to open registry %s (%s)\n",
                                state_path("registry.tdb"), strerror(errno) ));
-                       return false;
+                       return werr;
                }
                
                DEBUG(10,("regdb_init: Successfully created registry tdb\n"));
@@ -349,20 +410,22 @@ bool regdb_init(void)
        vers_id = dbwrap_fetch_int32(regdb, vstring);
 
        if ( vers_id != REGVER_V1 ) {
+               NTSTATUS status;
                /* any upgrade code here if needed */
                DEBUG(10, ("regdb_init: got %s = %d != %d\n", vstring,
                           vers_id, REGVER_V1));
-               if (dbwrap_store_int32(regdb, vstring, REGVER_V1) != 0) {
-                       DEBUG(0, ("regdb_init: error storing %s = %d\n",
-                                 vstring, REGVER_V1));
-                       return false;
+               status = dbwrap_trans_store_int32(regdb, vstring, REGVER_V1);
+               if (!NT_STATUS_IS_OK(status)) {
+                       DEBUG(1, ("regdb_init: error storing %s = %d: %s\n",
+                                 vstring, REGVER_V1, nt_errstr(status)));
+                       return ntstatus_to_werror(status);
                } else {
                        DEBUG(10, ("regdb_init: stored %s = %d\n",
                                  vstring, REGVER_V1));
                }
        }
 
-       return true;
+       return WERR_OK;
 }
 
 /***********************************************************************
@@ -381,7 +444,8 @@ WERROR regdb_open( void )
        
        become_root();
 
-       regdb = db_open(NULL, state_path("registry.tdb"), 0, REG_TDB_FLAGS, O_RDWR, 0600);
+       regdb = db_open(NULL, state_path("registry.tdb"), 0,
+                             REG_TDB_FLAGS, O_RDWR, 0600);
        if ( !regdb ) {
                result = ntstatus_to_werror( map_nt_error_from_unix( errno ) );
                DEBUG(0,("regdb_open: Failed to open %s! (%s)\n", 
@@ -472,21 +536,36 @@ static bool regdb_store_keys_internal(const char *key, REGSUBKEY_CTR *ctr)
        /* pack all the strings */
 
        for (i=0; i<num_subkeys; i++) {
-               len += tdb_pack(buffer+len, buflen-len, "f",
-                               regsubkey_ctr_specific_key(ctr, i));
-               if (len > buflen) {
-                       /* allocate some extra space */
-                       buffer = (uint8 *)SMB_REALLOC(buffer, len*2);
+               size_t thistime;
+
+               thistime = tdb_pack(buffer+len, buflen-len, "f",
+                                   regsubkey_ctr_specific_key(ctr, i));
+               if (len+thistime > buflen) {
+                       size_t thistime2;
+                       /*
+                        * tdb_pack hasn't done anything because of the short
+                        * buffer, allocate extra space.
+                        */
+                       buffer = SMB_REALLOC_ARRAY(buffer, uint8_t,
+                                                  (len+thistime)*2);
                        if(buffer == NULL) {
                                DEBUG(0, ("regdb_store_keys: Failed to realloc "
-                                         "memory of size [%d]\n", len*2));
+                                         "memory of size [%u]\n",
+                                         (unsigned int)(len+thistime)*2));
+                               ret = false;
+                               goto done;
+                       }
+                       buflen = (len+thistime)*2;
+                       thistime2 = tdb_pack(
+                               buffer+len, buflen-len, "f",
+                               regsubkey_ctr_specific_key(ctr, i));
+                       if (thistime2 != thistime) {
+                               DEBUG(0, ("tdb_pack failed\n"));
                                ret = false;
                                goto done;
                        }
-                       buflen = len*2;
-                       len = tdb_pack(buffer+len, buflen-len, "f",
-                                      regsubkey_ctr_specific_key(ctr, i));
                }
+               len += thistime;
        }
 
        /* finally write out the data */
@@ -499,6 +578,16 @@ static bool regdb_store_keys_internal(const char *key, REGSUBKEY_CTR *ctr)
                goto done;
        }
 
+       /*
+        * Delete a sorted subkey cache for regdb_key_exists, will be
+        * recreated automatically
+        */
+       keyname = talloc_asprintf(ctx, "%s/%s", REG_SORTED_SUBKEYS_PREFIX,
+                                 keyname);
+       if (keyname != NULL) {
+               dbwrap_delete_bystring(regdb, keyname);
+       }
+
 done:
        TALLOC_FREE(ctx);
        SAFE_FREE(buffer);
@@ -519,6 +608,10 @@ bool regdb_store_keys(const char *key, REGSUBKEY_CTR *ctr)
        TALLOC_CTX *ctx = talloc_stackframe();
        NTSTATUS status;
 
+       if (!regdb_key_is_base_key(key) && !regdb_key_exists(key)) {
+               goto fail;
+       }
+
        /*
         * fetch a list of the old subkeys so we can determine if anything has
         * changed
@@ -552,7 +645,7 @@ bool regdb_store_keys(const char *key, REGSUBKEY_CTR *ctr)
 
        TALLOC_FREE(old_subkeys);
 
-       if (regdb->transaction_start(regdb) == -1) {
+       if (regdb->transaction_start(regdb) != 0) {
                DEBUG(0, ("regdb_store_keys: transaction_start failed\n"));
                goto fail;
        }
@@ -568,15 +661,28 @@ bool regdb_store_keys(const char *key, REGSUBKEY_CTR *ctr)
 
        regdb_fetch_keys(key, old_subkeys);
 
-       /* store the subkey list for the parent */
-
-       if (!regdb_store_keys_internal(key, ctr) ) {
-               DEBUG(0,("regdb_store_keys: Failed to store new subkey list "
-                        "for parent [%s]\n", key));
-               goto cancel;
-       }
+       /*
+        * Make the store operation as safe as possible without transactions:
+        *
+        * (1) For each subkey removed from ctr compared with old_subkeys:
+        *
+        *     (a) First delete the value db entry.
+        *
+        *     (b) Next delete the secdesc db record.
+        *
+        *     (c) Then delete the subkey list entry.
+        *
+        * (2) Now write the list of subkeys of the parent key,
+        *     deleting removed entries and adding new ones.
+        *
+        * (3) Finally create the subkey list entries for the added keys.
+        *
+        * This way if we crash half-way in between deleting the subkeys
+        * and storing the parent's list of subkeys, no old data can pop up
+        * out of the blue when re-adding keys later on.
+        */
 
-       /* now delete removed keys */
+       /* (1) delete removed keys' lists (values/secdesc/subkeys) */
 
        num_subkeys = regsubkey_ctr_numkeys(old_subkeys);
        for (i=0; i<num_subkeys; i++) {
@@ -590,7 +696,12 @@ bool regdb_store_keys(const char *key, REGSUBKEY_CTR *ctr)
                        continue;
                }
 
-               path = talloc_asprintf(ctx, "%s/%s", key, oldkeyname);
+               /* (a) Delete the value list for this key */
+
+               path = talloc_asprintf(ctx, "%s/%s/%s",
+                               REG_VALUE_PREFIX,
+                               key,
+                               oldkeyname );
                if (!path) {
                        goto cancel;
                }
@@ -598,15 +709,14 @@ bool regdb_store_keys(const char *key, REGSUBKEY_CTR *ctr)
                if (!path) {
                        goto cancel;
                }
-               status = dbwrap_delete_bystring(regdb, path);
-               if (!NT_STATUS_IS_OK(status)) {
-                       DEBUG(1, ("Deleting %s failed\n", path));
-                       goto cancel;
-               }
-
+               /* Ignore errors here, we might have no values around */
+               dbwrap_delete_bystring(regdb, path);
                TALLOC_FREE(path);
+
+               /* (b) Delete the secdesc for this key */
+
                path = talloc_asprintf(ctx, "%s/%s/%s",
-                               REG_VALUE_PREFIX,
+                               REG_SECDESC_PREFIX,
                                key,
                                oldkeyname );
                if (!path) {
@@ -616,17 +726,50 @@ bool regdb_store_keys(const char *key, REGSUBKEY_CTR *ctr)
                if (!path) {
                        goto cancel;
                }
+               status = dbwrap_delete_bystring(regdb, path);
+               /* Don't fail if there are no values around. */
+               if (!NT_STATUS_IS_OK(status) &&
+                   !NT_STATUS_EQUAL(status, NT_STATUS_NOT_FOUND))
+               {
+                       DEBUG(1, ("Deleting %s failed: %s\n", path,
+                                 nt_errstr(status)));
+                       goto cancel;
+               }
+               TALLOC_FREE(path);
 
-               /*
-                * Ignore errors here, we might have no values around
-                */
-               dbwrap_delete_bystring(regdb, path);
+               /* (c) Delete the list of subkeys of this key */
+
+               path = talloc_asprintf(ctx, "%s/%s", key, oldkeyname);
+               if (!path) {
+                       goto cancel;
+               }
+               path = normalize_reg_path(ctx, path);
+               if (!path) {
+                       goto cancel;
+               }
+               status = dbwrap_delete_bystring(regdb, path);
+               /* Don't fail if the subkey record was not found. */
+               if (!NT_STATUS_IS_OK(status) &&
+                   !NT_STATUS_EQUAL(status, NT_STATUS_NOT_FOUND))
+               {
+                       DEBUG(1, ("Deleting %s failed: %s\n", path,
+                                 nt_errstr(status)));
+                       goto cancel;
+               }
                TALLOC_FREE(path);
        }
 
        TALLOC_FREE(old_subkeys);
 
-       /* now create records for any subkeys that don't already exist */
+       /* (2) store the subkey list for the parent */
+
+       if (!regdb_store_keys_internal(key, ctr) ) {
+               DEBUG(0,("regdb_store_keys: Failed to store new subkey list "
+                        "for parent [%s]\n", key));
+               goto cancel;
+       }
+
+       /* (3) now create records for any subkeys that don't already exist */
 
        num_subkeys = regsubkey_ctr_numkeys(ctr);
 
@@ -670,7 +813,7 @@ bool regdb_store_keys(const char *key, REGSUBKEY_CTR *ctr)
                TALLOC_FREE(path);
        }
 
-       if (regdb->transaction_commit(regdb) == -1) {
+       if (regdb->transaction_commit(regdb) != 0) {
                DEBUG(0, ("regdb_store_keys: Could not commit transaction\n"));
                goto fail;
        }
@@ -679,7 +822,7 @@ bool regdb_store_keys(const char *key, REGSUBKEY_CTR *ctr)
        return true;
 
 cancel:
-       if (regdb->transaction_cancel(regdb) == -1) {
+       if (regdb->transaction_cancel(regdb) != 0) {
                smb_panic("regdb_store_keys: transaction_cancel failed\n");
        }
 
@@ -690,6 +833,286 @@ fail:
 }
 
 
+static TDB_DATA regdb_fetch_key_internal(TALLOC_CTX *mem_ctx, const char *key)
+{
+       char *path = NULL;
+       TDB_DATA data;
+
+       path = normalize_reg_path(mem_ctx, key);
+       if (!path) {
+               return make_tdb_data(NULL, 0);
+       }
+
+       data = dbwrap_fetch_bystring(regdb, mem_ctx, path);
+
+       TALLOC_FREE(path);
+       return data;
+}
+
+
+/**
+ * check whether a given key name represents a base key,
+ * i.e one without a subkey separator ('/' or '\').
+ */
+static bool regdb_key_is_base_key(const char *key)
+{
+       TALLOC_CTX *mem_ctx = talloc_stackframe();
+       bool ret = false;
+       char *path;
+
+       if (key == NULL) {
+               goto done;
+       }
+
+       path = normalize_reg_path(mem_ctx, key);
+       if (path == NULL) {
+               DEBUG(0, ("out of memory! (talloc failed)\n"));
+               goto done;
+       }
+
+       if (*path == '\0') {
+               goto done;
+       }
+
+       ret = (strrchr(path, '/') == NULL);
+
+done:
+       TALLOC_FREE(mem_ctx);
+       return ret;
+}
+
+/*
+ * regdb_key_exists() is a very frequent operation. It can be quite
+ * time-consuming to fully fetch the parent's subkey list, talloc_strdup all
+ * subkeys and then compare the keyname linearly to all the parent's subkeys.
+ *
+ * The following code tries to make this operation as efficient as possible:
+ * Per registry key we create a list of subkeys that is very efficient to
+ * search for existence of a subkey. Its format is:
+ *
+ * 4 bytes num_subkeys
+ * 4*num_subkey bytes offset into the string array
+ * then follows a sorted list of subkeys in uppercase
+ *
+ * This record is created by create_sorted_subkeys() on demand if it does not
+ * exist. scan_parent_subkeys() uses regdb->parse_record to search the sorted
+ * list, the parsing code and the binary search can be found in
+ * parent_subkey_scanner. The code uses parse_record() to avoid a memcpy of
+ * the potentially large subkey record.
+ *
+ * The sorted subkey record is deleted in regdb_store_keys_internal and
+ * recreated on demand.
+ */
+
+static int cmp_keynames(const void *p1, const void *p2)
+{
+       return StrCaseCmp(*((char **)p1), *((char **)p2));
+}
+
+static bool create_sorted_subkeys(const char *key, const char *sorted_keyname)
+{
+       char **sorted_subkeys;
+       REGSUBKEY_CTR *ctr;
+       bool result = false;
+       NTSTATUS status;
+       char *buf;
+       char *p;
+       int i, res;
+       size_t len;
+
+       ctr = talloc(talloc_tos(), REGSUBKEY_CTR);
+       if (ctr == NULL) {
+               return false;
+       }
+
+       res = regdb_fetch_keys(key, ctr);
+       if (res == -1) {
+               goto fail;
+       }
+
+       sorted_subkeys = talloc_array(ctr, char *, ctr->num_subkeys);
+       if (sorted_subkeys == NULL) {
+               goto fail;
+       }
+
+       len = 4 + 4*ctr->num_subkeys;
+
+       for (i = 0; i<ctr->num_subkeys; i++) {
+               sorted_subkeys[i] = talloc_strdup_upper(sorted_subkeys,
+                                                       ctr->subkeys[i]);
+               if (sorted_subkeys[i] == NULL) {
+                       goto fail;
+               }
+               len += strlen(sorted_subkeys[i])+1;
+       }
+
+       qsort(sorted_subkeys, ctr->num_subkeys, sizeof(char *), cmp_keynames);
+
+       buf = talloc_array(ctr, char, len);
+       if (buf == NULL) {
+               goto fail;
+       }
+       p = buf + 4 + 4*ctr->num_subkeys;
+
+       SIVAL(buf, 0, ctr->num_subkeys);
+
+       for (i=0; i<ctr->num_subkeys; i++) {
+               ptrdiff_t offset = p - buf;
+               SIVAL(buf, 4 + 4*i, offset);
+               strlcpy(p, sorted_subkeys[i], len-offset);
+               p += strlen(sorted_subkeys[i]) + 1;
+       }
+
+       status = dbwrap_trans_store_bystring(
+               regdb, sorted_keyname, make_tdb_data((uint8_t *)buf, len),
+               TDB_REPLACE);
+       if (!NT_STATUS_IS_OK(status)) {
+               goto fail;
+       }
+
+       result = true;
+ fail:
+       TALLOC_FREE(ctr);
+       return result;
+}
+
+struct scan_subkey_state {
+       char *name;
+       bool scanned;
+       bool found;
+};
+
+static int parent_subkey_scanner(TDB_DATA key, TDB_DATA data,
+                                void *private_data)
+{
+       struct scan_subkey_state *state =
+               (struct scan_subkey_state *)private_data;
+       uint32_t num_subkeys;
+       uint32_t l, u;
+
+       if (data.dsize < sizeof(uint32_t)) {
+               return -1;
+       }
+
+       state->scanned = true;
+       state->found = false;
+
+       tdb_unpack(data.dptr, data.dsize, "d", &num_subkeys);
+
+       l = 0;
+       u = num_subkeys;
+
+       while (l < u) {
+               uint32_t idx = (l+u)/2;
+               char *s = (char *)data.dptr + IVAL(data.dptr, 4 + 4*idx);
+               int comparison = strcmp(state->name, s);
+
+               if (comparison < 0) {
+                       u = idx;
+               } else if (comparison > 0) {
+                       l = idx + 1;
+               } else {
+                       state->found = true;
+                       return 0;
+               }
+       }
+       return 0;
+}
+
+static bool scan_parent_subkeys(const char *parent, const char *name)
+{
+       char *path = NULL;
+       char *key = NULL;
+       struct scan_subkey_state state = { 0, };
+       bool result = false;
+       int res;
+
+       state.name = NULL;
+
+       path = normalize_reg_path(talloc_tos(), parent);
+       if (path == NULL) {
+               goto fail;
+       }
+
+       key = talloc_asprintf(talloc_tos(), "%s/%s",
+                             REG_SORTED_SUBKEYS_PREFIX, path);
+       if (key == NULL) {
+               goto fail;
+       }
+
+       state.name = talloc_strdup_upper(talloc_tos(), name);
+       if (state.name == NULL) {
+               goto fail;
+       }
+       state.scanned = false;
+
+       res = regdb->parse_record(regdb, string_term_tdb_data(key),
+                                 parent_subkey_scanner, &state);
+
+       if (state.scanned) {
+               result = state.found;
+       } else {
+               if (!create_sorted_subkeys(path, key)) {
+                       goto fail;
+               }
+               res = regdb->parse_record(regdb, string_term_tdb_data(key),
+                                         parent_subkey_scanner, &state);
+               if ((res == 0) && (state.scanned)) {
+                       result = state.found;
+               }
+       }
+
+ fail:
+       TALLOC_FREE(path);
+       TALLOC_FREE(state.name);
+       return result;
+}
+
+/**
+ * Check for the existence of a key.
+ *
+ * Existence of a key is authoritatively defined by its
+ * existence in the list of subkeys of its parent key.
+ * The exeption of this are keys without a parent key,
+ * i.e. the "base" keys (HKLM, HKCU, ...).
+ */
+static bool regdb_key_exists(const char *key)
+{
+       TALLOC_CTX *mem_ctx = talloc_stackframe();
+       TDB_DATA value;
+       bool ret = false;
+       char *path, *p;
+
+       if (key == NULL) {
+               goto done;
+       }
+
+       path = normalize_reg_path(mem_ctx, key);
+       if (path == NULL) {
+               DEBUG(0, ("out of memory! (talloc failed)\n"));
+               goto done;
+       }
+
+       if (*path == '\0') {
+               goto done;
+       }
+
+       p = strrchr(path, '/');
+       if (p == NULL) {
+               /* this is a base key */
+               value = regdb_fetch_key_internal(mem_ctx, path);
+               ret = (value.dptr != NULL);
+       } else {
+               *p = '\0';
+               ret = scan_parent_subkeys(path, p+1);
+       }
+
+done:
+       TALLOC_FREE(mem_ctx);
+       return ret;
+}
+
+
 /***********************************************************************
  Retrieve an array of strings containing subkeys.  Memory should be
  released by the caller.
@@ -697,7 +1120,6 @@ fail:
 
 int regdb_fetch_keys(const char *key, REGSUBKEY_CTR *ctr)
 {
-       char *path = NULL;
        uint32 num_items;
        uint8 *buf;
        uint32 buflen, len;
@@ -705,49 +1127,66 @@ int regdb_fetch_keys(const char *key, REGSUBKEY_CTR *ctr)
        fstring subkeyname;
        int ret = -1;
        TALLOC_CTX *frame = talloc_stackframe();
-       struct db_record *rec;
+       TDB_DATA value;
 
        DEBUG(11,("regdb_fetch_keys: Enter key => [%s]\n", key ? key : "NULL"));
 
-       path = talloc_strdup(frame, key);
-       if (!path) {
-               goto fail;
+       if (!regdb_key_exists(key)) {
+               goto done;
        }
 
-       /* convert to key format */
-       path = talloc_string_sub(frame, path, "\\", "/");
-       if (!path) {
-               goto fail;
-       }
-       strupper_m(path);
+       ctr->seqnum = regdb_get_seqnum();
 
-       rec = regdb->fetch_locked(regdb, frame, string_term_tdb_data(path));
-       if (rec == NULL) {
+       value = regdb_fetch_key_internal(frame, key);
+
+       if (value.dptr == NULL) {
+               DEBUG(10, ("regdb_fetch_keys: no subkeys found for key [%s]\n",
+                          key));
                ret = 0;
-               goto fail;
+               goto done;
        }
 
-       ctr->seqnum = regdb_get_seqnum();
+       buf = value.dptr;
+       buflen = value.dsize;
+       len = tdb_unpack( buf, buflen, "d", &num_items);
 
-       buf = rec->value.dptr;
-       buflen = rec->value.dsize;
+       /*
+        * The following code breaks the abstraction that reg_objects.c sets
+        * up with regsubkey_ctr_addkey(). But if we use that with the current
+        * data structure of ctr->subkeys being an unsorted array, we end up
+        * with an O(n^2) algorithm for retrieving keys from the tdb
+        * file. This is pretty pointless, as we have to trust the data
+        * structure on disk not to have duplicates anyway. The alternative to
+        * breaking this abstraction would be to set up a more sophisticated
+        * data structure in REGSUBKEY_CTR.
+        *
+        * This makes "net conf list" for a registry with >1000 shares
+        * actually usable :-)
+        */
 
-       if ( !buf ) {
-               DEBUG(5,("regdb_fetch_keys: tdb lookup failed to locate key [%s]\n", key));
-               goto fail;
+       ctr->subkeys = talloc_array(ctr, char *, num_items);
+       if (ctr->subkeys == NULL) {
+               DEBUG(5, ("regdb_fetch_keys: could not allocate subkeys\n"));
+               goto done;
        }
-
-       len = tdb_unpack( buf, buflen, "d", &num_items);
+       ctr->num_subkeys = num_items;
 
        for (i=0; i<num_items; i++) {
                len += tdb_unpack(buf+len, buflen-len, "f", subkeyname);
-               regsubkey_ctr_addkey(ctr, subkeyname);
+               ctr->subkeys[i] = talloc_strdup(ctr->subkeys, subkeyname);
+               if (ctr->subkeys[i] == NULL) {
+                       DEBUG(5, ("regdb_fetch_keys: could not allocate "
+                                 "subkeyname\n"));
+                       TALLOC_FREE(ctr->subkeys);
+                       ctr->num_subkeys = 0;
+                       goto done;
+               }
        }
 
        DEBUG(11,("regdb_fetch_keys: Exit [%d] items\n", num_items));
 
        ret = num_items;
- fail:
+done:
        TALLOC_FREE(frame);
        return ret;
 }
@@ -840,33 +1279,30 @@ int regdb_fetch_values( const char* key, REGVAL_CTR *values )
 {
        char *keystr = NULL;
        TALLOC_CTX *ctx = talloc_stackframe();
-       struct db_record *rec;
        int ret = 0;
+       TDB_DATA value;
 
        DEBUG(10,("regdb_fetch_values: Looking for value of key [%s] \n", key));
 
-       keystr = talloc_asprintf(ctx, "%s/%s", REG_VALUE_PREFIX, key);
-       if (!keystr) {
-               return 0;
-       }
-       keystr = normalize_reg_path(ctx, keystr);
-       if (!keystr) {
+       if (!regdb_key_exists(key)) {
                goto done;
        }
 
-       rec = regdb->fetch_locked(regdb, ctx, string_term_tdb_data(keystr));
-       if (rec == NULL) {
+       keystr = talloc_asprintf(ctx, "%s/%s", REG_VALUE_PREFIX, key);
+       if (!keystr) {
                goto done;
        }
 
        values->seqnum = regdb_get_seqnum();
 
-       if (!rec->value.dptr) {
+       value = regdb_fetch_key_internal(ctx, keystr);
+
+       if (!value.dptr) {
                /* all keys have zero values by default */
                goto done;
        }
 
-       regdb_unpack_values(values, rec->value.dptr, rec->value.dsize);
+       regdb_unpack_values(values, value.dptr, value.dsize);
        ret = regval_ctr_numvals(values);
 
 done:
@@ -879,11 +1315,16 @@ bool regdb_store_values( const char *key, REGVAL_CTR *values )
        TDB_DATA old_data, data;
        char *keystr = NULL;
        TALLOC_CTX *ctx = talloc_stackframe();
-       int len, ret;
+       int len;
+       NTSTATUS status;
        bool result = false;
 
        DEBUG(10,("regdb_store_values: Looking for value of key [%s] \n", key));
 
+       if (!regdb_key_exists(key)) {
+               goto done;
+       }
+
        ZERO_STRUCT(data);
 
        len = regdb_pack_values(values, data.dptr, data.dsize);
@@ -918,9 +1359,9 @@ bool regdb_store_values( const char *key, REGVAL_CTR *values )
                goto done;
        }
 
-       ret = dbwrap_trans_store(regdb, string_term_tdb_data(keystr), data,
-                                TDB_REPLACE);
-       result = (ret != -1);
+       status = dbwrap_trans_store_bystring(regdb, keystr, data, TDB_REPLACE);
+
+       result = NT_STATUS_IS_OK(status);
 
 done:
        TALLOC_FREE(ctx);
@@ -938,6 +1379,11 @@ static WERROR regdb_get_secdesc(TALLOC_CTX *mem_ctx, const char *key,
 
        DEBUG(10, ("regdb_get_secdesc: Getting secdesc of key [%s]\n", key));
 
+       if (!regdb_key_exists(key)) {
+               err = WERR_BADFILE;
+               goto done;
+       }
+
        tdbkey = talloc_asprintf(tmp_ctx, "%s/%s", REG_SECDESC_PREFIX, key);
        if (tdbkey == NULL) {
                err = WERR_NOMEM;
@@ -970,9 +1416,14 @@ static WERROR regdb_set_secdesc(const char *key,
 {
        TALLOC_CTX *mem_ctx = talloc_stackframe();
        char *tdbkey;
+       NTSTATUS status;
        WERROR err = WERR_NOMEM;
        TDB_DATA tdbdata;
-       int tdb_ret;
+
+       if (!regdb_key_exists(key)) {
+               err = WERR_BADFILE;
+               goto done;
+       }
 
        tdbkey = talloc_asprintf(mem_ctx, "%s/%s", REG_SECDESC_PREFIX, key);
        if (tdbkey == NULL) {
@@ -982,12 +1433,11 @@ static WERROR regdb_set_secdesc(const char *key,
 
        if (secdesc == NULL) {
                /* assuming a delete */
-               tdb_ret = dbwrap_trans_delete(regdb,
-                                             string_term_tdb_data(tdbkey));
-               if (tdb_ret == -1) {
-                       err = ntstatus_to_werror(map_nt_error_from_unix(errno));
-               } else {
+               status = dbwrap_trans_delete_bystring(regdb, tdbkey);
+               if (NT_STATUS_IS_OK(status)) {
                        err = WERR_OK;
+               } else {
+                       err = ntstatus_to_werror(status);
                }
                goto done;
        }
@@ -999,10 +1449,9 @@ static WERROR regdb_set_secdesc(const char *key,
                goto done;
        }
 
-       tdb_ret = dbwrap_trans_store(regdb, string_term_tdb_data(tdbkey),
-                                    tdbdata, 0);
-       if (tdb_ret == -1) {
-               err = ntstatus_to_werror(map_nt_error_from_unix(errno));
+       status = dbwrap_trans_store_bystring(regdb, tdbkey, tdbdata, 0);
+       if (!NT_STATUS_IS_OK(status)) {
+               err = ntstatus_to_werror(status);
                goto done;
        }