bin/65042: [patch] Minimize CPU cycles used by ls(1) when processing ACLs

[Christian S.J.Peron]

>Number:         65042
>Category:       bin
>Synopsis:       [patch] Minimize CPU cycles used by ls(1) when processing ACLs
>Confidential:   no
>Severity:       non-critical
>Priority:       low
>Responsible:    freebsd-bugs
>State:          open
>Quarter:        
>Keywords:       
>Date-Required:
>Class:          change-request
>Submitter-Id:   current-users
>Arrival-Date:   Thu Apr 01 08:00:35 PST 2004
>Closed-Date:
>Last-Modified:
>Originator:     Christian S.J. Peron
>Release:        FreeBSD 5.2.1-RELEASE-p3 i386
>Organization:
>Environment:
System: FreeBSD dev 5.2.1-RELEASE-p3 FreeBSD 5.2.1-RELEASE-p3 #5: Tue Mar 23 00:19:58 GMT 2004     cperon at dev:/usr/src/sys/i386/compile/XOR  i386 

	
>Description:
	Currently ls(1) will iterate through every ACL associated with a
	file when it determines whether or not the file has implemented
	extended ACLs.

	In reality with access ACLs, (being an extension of
	regular file permissions) the loop could terminate once it detects
	greater than 3 ACLs for the file.

	This makes the loop O(4) rather than O(n).
 
>How-To-Repeat:
	N/A
>Fix:
--- bin/ls/print.c.bak	Thu Apr  1 15:09:14 2004
+++ bin/ls/print.c	Thu Apr  1 15:20:16 2004
@@ -694,11 +694,16 @@
 	*haveacls = 1;
 	if ((facl = acl_get_file(name, ACL_TYPE_ACCESS)) != NULL) {
 		if (acl_get_entry(facl, ACL_FIRST_ENTRY, &ae) == 1) {
-			entries = 0;
-			do
-				entries++;
-			while (acl_get_entry(facl, ACL_NEXT_ENTRY, &ae) == 1);
-			if (entries != 3)
+			entries = 1;
+			while (acl_get_entry(facl, ACL_NEXT_ENTRY, &ae) == 1) 
+				if (entries++ > 3)
+					break;
+			/*
+			 * POSIX.1e requires that ACLs of type ACL_TYPE_ACCESS
+			 * must have at least three entries owner, group and other.
+			 * So anything with more than 3 ACLs looks interesting to us.
+			 */
+			if (entries > 3)
 				buf[10] = '+';
 		}
 		acl_free(facl);
>Release-Note:
>Audit-Trail:
>Unformatted: