Further improved ACL algorithm for picking categories

(cherry picked from commit 411bcf1a41d2758823d17e0864ef45e5f3948b7a)

2 files changed, 62 insertions, 31 deletions

diff --git a/src/acl.c b/src/acl.c
index e0fd3f728..09a7c2181 100644
--- a/src/acl.c
+++ b/src/acl.c
@@ -475,36 +475,61 @@ sds ACLDescribeUserCommandRules(user *u) {
         ACLSetUser(fakeuser,"-@all",-1);
     }
 
-    /* Try to add or subtract each category one after the other. Often a
-     * single category will not perfectly match the set of commands into
-     * it, so at the end we do a final pass adding/removing the single commands
-     * needed to make the bitmap exactly match. A temp user is maintained to
-     * keep track of categories already applied. */
+    /* Attempt to find a good approximation for categories and commands
+     * based on the current bits used, by looping over the category list
+     * and applying the best fit each time. Often a set of categories will not 
+     * perfectly match the set of commands into it, so at the end we do a 
+     * final pass adding/removing the single commands needed to make the bitmap
+     * exactly match. A temp user is maintained to keep track of categories 
+     * already applied. */
     user tu = {0};
     user *tempuser = &tu;
     memcpy(tempuser->allowed_commands,
         u->allowed_commands, 
         sizeof(u->allowed_commands));
-
-    for (int j = 0; ACLCommandCategories[j].flag != 0; j++) {
-        unsigned long on, off;
-        ACLCountCategoryBitsForUser(tempuser,&on,&off,ACLCommandCategories[j].name);
-        if ((additive && on > off) || (!additive && off > on)) {
-            sds op = sdsnewlen(additive ? "+@" : "-@", 2);
-            op = sdscat(op,ACLCommandCategories[j].name);
-            ACLSetUser(fakeuser,op,-1);
-
-            sds invop = sdsnewlen(additive ? "-@" : "+@", 2);
-            invop = sdscat(invop,ACLCommandCategories[j].name);
-            ACLSetUser(tempuser,invop,-1);
-
-            rules = sdscatsds(rules,op);
-            rules = sdscatlen(rules," ",1);
-            sdsfree(op);
-            sdsfree(invop);
+    while (1) {
+        int best = -1;
+        unsigned long mindiff = INT_MAX, maxsame = 0;
+        for (int j = 0; ACLCommandCategories[j].flag != 0; j++) {
+            unsigned long on, off, diff, same;
+            ACLCountCategoryBitsForUser(tempuser,&on,&off,ACLCommandCategories[j].name);
+
+            /* Check if the current category is the best this loop:
+             * * It has more commands in common with the user than commands
+             *   that are different.
+             * AND EITHER
+             * * It has the fewest number of differences
+             *    than the best match we have found so far. 
+             * * OR it matches the fewest number of differences
+             *   that we've seen but it has more in common. */
+            diff = additive ? off : on;
+            same = additive ? on : off;
+            if (same > diff && 
+                    ((diff < mindiff) || (diff == mindiff && same > maxsame))) {
+                best = j;
+                mindiff = diff;
+                maxsame = same;
+            }
         }
+
+        /* We didn't find a match */
+        if (best == -1) break;
+
+        sds op = sdsnewlen(additive ? "+@" : "-@", 2);
+        op = sdscat(op,ACLCommandCategories[best].name);
+        ACLSetUser(fakeuser,op,-1);
+
+        sds invop = sdsnewlen(additive ? "-@" : "+@", 2);
+        invop = sdscat(invop,ACLCommandCategories[best].name);
+        ACLSetUser(tempuser,invop,-1);
+
+        rules = sdscatsds(rules,op);
+        rules = sdscatlen(rules," ",1);
+        sdsfree(op);
+        sdsfree(invop);
     }
 
+
     /* Fix the final ACLs with single commands differences. */
     dictIterator *di = dictGetIterator(server.orig_commands);
     dictEntry *de;
diff --git a/tests/unit/acl.tcl b/tests/unit/acl.tcl
index 12f59e749..d35a012f4 100644
--- a/tests/unit/acl.tcl
+++ b/tests/unit/acl.tcl
@@ -138,15 +138,21 @@ start_server {tags {"acl"}} {
     # A regression test make sure that as long as there is a simple
     # category defining the commands, that it will be used as is.
     test {ACL GETUSER provides reasonable results} {
-        # Test for future commands where allowed
-        r ACL setuser additive reset +@all -@write
-        set cmdstr [dict get [r ACL getuser additive] commands]
-        assert_match {+@all -@write} $cmdstr
-
-        # Test for future commands are disallowed
-        r ACL setuser subtractive reset -@all +@read
-        set cmdstr [dict get [r ACL getuser subtractive] commands]
-        assert_match {-@all +@read} $cmdstr
+        set categories [r ACL CAT]
+
+        # Test that adding each single category will
+        # result in just that category with both +@all and -@all
+        foreach category $categories {
+            # Test for future commands where allowed
+            r ACL setuser additive reset +@all "-@$category"
+            set cmdstr [dict get [r ACL getuser additive] commands]
+            assert_equal "+@all -@$category" $cmdstr
+
+            # Test for future commands where disallowed
+            r ACL setuser restrictive reset -@all "+@$category"
+            set cmdstr [dict get [r ACL getuser restrictive] commands]
+            assert_equal "-@all +@$category" $cmdstr
+        }
     }
 
     test {ACL #5998 regression: memory leaks adding / removing subcommands} {