Revision: 1446 http://trac.macosforge.org/projects/calendarserver/changeset/1446 Author: cdaboo@apple.com Date: 2007-04-04 07:46:26 -0700 (Wed, 04 Apr 2007) Log Message: ----------- Merge of branches/users/cdaboo/fast-multiget-1425. One minor change to the fast acl look was done to fix an issue with making sure that different acl values actual resulted in different map entries. This did not affect overall performance (i.e. new implementation is still better than old). Modified Paths: -------------- CalendarServer/trunk/twistedcaldav/extensions.py CalendarServer/trunk/twistedcaldav/index.py CalendarServer/trunk/twistedcaldav/method/report_calquery.py CalendarServer/trunk/twistedcaldav/method/report_common.py CalendarServer/trunk/twistedcaldav/method/report_multiget.py Modified: CalendarServer/trunk/twistedcaldav/extensions.py =================================================================== --- CalendarServer/trunk/twistedcaldav/extensions.py 2007-04-03 19:49:36 UTC (rev 1445) +++ CalendarServer/trunk/twistedcaldav/extensions.py 2007-04-04 14:46:26 UTC (rev 1446) @@ -27,6 +27,7 @@ "SudoAuthIDMixin", ] +import cPickle as pickle import urllib import cgi import time @@ -44,6 +45,7 @@ from twisted.web2.dav.static import DAVFile as SuperDAVFile from twisted.web2.dav.resource import DAVResource as SuperDAVResource from twisted.web2.dav.resource import DAVPrincipalResource as SuperDAVPrincipalResource +from twisted.web2.dav.util import joinURL from twistedcaldav.directory.sudo import SudoDirectoryService @@ -74,7 +76,171 @@ Extended L{twisted.web2.dav.resource.DAVResource} implementation. """ + def findChildrenFaster(self, depth, request, okcallback, badcallback, names, privileges, inherited_aces): + """ + See L{IDAVResource.findChildren}. + This implementation works for C{depth} values of C{"0"}, C{"1"}, + and C{"infinity"}. As long as C{self.listChildren} is implemented + + @param depth: a C{str} for the depth: "0", "1" and "infinity" only allowed. + @param request: the L{Request} for the current request in progress + @param okcallback: a callback function used on all resources that pass the privilege check, + or C{None} + @param badcallback: a callback function used on all resources that fail the privilege check, + or C{None} + @param names: a C{list} of C{str}'s containing the names of the child resources to lookup. If + empty or C{None} all children will be examined, otherwise only the ones in the list. + @param privileges: a list of privileges to check. + @param inherited_aces: the list of parent ACEs that are inherited by all children. + """ + assert depth in ("0", "1", "infinity"), "Invalid depth: %s" % (depth,) + + if depth == "0" or not self.isCollection(): + yield None + + # First find all depth 1 children + #children = [] + #d = waitForDeferred(self.findChildren("1", request, lambda x, y: children.append((x, y)), privileges=None, inherited_aces=None)) + #yield d + #d.getResult() + + children = [] + basepath = request.urlForResource(self) + childnames = list(self.listChildren()) + for childname in childnames: + if names and childname not in names: + continue + childpath = joinURL(basepath, childname) + d = waitForDeferred(request.locateChildResource(self, childname)) + yield d + child = d.getResult() + if child is None: + children.append((None, childpath + "/")) + else: + if child.isCollection(): + children.append((child, childpath + "/")) + else: + children.append((child, childpath)) + + # Generate (acl,supported_privs) map + aclmap = {} + for resource, url in children: + acl = waitForDeferred(resource.accessControlList(request, inheritance=False, inherited_aces=inherited_aces)) + yield acl + acl = acl.getResult() + supportedPrivs = waitForDeferred(resource.supportedPrivileges(request)) + yield supportedPrivs + supportedPrivs = supportedPrivs.getResult() + aclmap.setdefault((pickle.dumps(acl), supportedPrivs), (acl, supportedPrivs, []))[2].append((resource, url)) + + # Now determine whether each ace satisfies privileges + #print aclmap + allowed_collections = [] + for items in aclmap.itervalues(): + checked = waitForDeferred(self.checkACLPrivilege(request, items[0], items[1], privileges, inherited_aces)) + yield checked + checked = checked.getResult() + if checked: + for resource, url in items[2]: + if okcallback: + okcallback(resource, url) + if resource.isCollection(): + allowed_collections.append((resource, url)) + else: + if badcallback: + for resource, url in items[2]: + badcallback(resource, url) + + # TODO: Depth: inifinity support + if depth == "infinity": + for collection, url in allowed_collections: + d = waitForDeferred(collection.findChildrenFaster(request, depth, okcallback, badcallback, names, privileges, inherited_aces=None)) + yield d + d.getResult() + + yield None + + findChildrenFaster = deferredGenerator(findChildrenFaster) + + def checkACLPrivilege(self, request, acl, privyset, privileges, inherited_aces): + + principal = self.currentPrincipal(request) + + # Other principal types don't make sense as actors. + assert ( + principal.children[0].name in ("unauthenticated", "href"), + "Principal is not an actor: %r" % (principal,) + ) + + acl = self.fullAccessControlList(acl, inherited_aces) + + pending = list(privileges) + denied = [] + + for ace in acl.children: + for privilege in tuple(pending): + if not self.matchPrivilege(davxml.Privilege(privilege), ace.privileges, privyset): + continue + + match = waitForDeferred(self.matchPrincipal(principal, ace.principal, request)) + yield match + match = match.getResult() + + if match: + if ace.invert: + continue + else: + if not ace.invert: + continue + + pending.remove(privilege) + + if not ace.allow: + denied.append(privilege) + + yield len(denied) + len(pending) == 0 + + checkACLPrivilege = deferredGenerator(checkACLPrivilege) + + def fullAccessControlList(self, acl, inherited_aces): + """ + See L{IDAVResource.accessControlList}. + + This implementation looks up the ACL in the private property + C{(L{twisted_private_namespace}, "acl")}. + If no ACL has been stored for this resource, it returns the value + returned by C{defaultAccessControlList}. + If access is disabled it will return C{None}. + """ + # + # Inheritance is problematic. Here is what we do: + # + # 1. A private element <Twisted:inheritable> is defined for use inside + # of a <DAV:ace>. This private element is removed when the ACE is + # exposed via WebDAV. + # + # 2. When checking ACLs with inheritance resolution, the server must + # examine all parent resources of the current one looking for any + # <Twisted:inheritable> elements. + # + # If those are defined, the relevant ace is applied to the ACL on the + # current resource. + # + + # Dynamically update privileges for those ace's that are inherited. + if acl: + aces = list(acl.children) + else: + aces = [] + + aces.extend(inherited_aces) + + acl = davxml.ACL(*aces) + + return acl + + class DAVPrincipalResource (SuperDAVPrincipalResource): """ Extended L{twisted.web2.dav.static.DAVFile} implementation. Modified: CalendarServer/trunk/twistedcaldav/index.py =================================================================== --- CalendarServer/trunk/twistedcaldav/index.py 2007-04-03 19:49:36 UTC (rev 1445) +++ CalendarServer/trunk/twistedcaldav/index.py 2007-04-04 14:46:26 UTC (rev 1446) @@ -44,6 +44,8 @@ from twistedcaldav.query import calendarquery from twistedcaldav import caldavxml +from vobject.icalendar import utc + db_basename = ".db.sqlite" schema_version = "4" collection_types = {"Calendar": "Regular Calendar Collection", "iTIP": "iTIP Calendar Collection"} @@ -218,6 +220,29 @@ uid = self._db_value_for_sql("select UID from RESOURCE where NAME = :1", name) return uid is not None + def resourcesExist(self, names): + """ + Determines whether the specified resource name exists in the index. + @param names: a C{list} containing the names of the resources to test + @return: a C{list} of all names that exist + """ + statement = "select NAME from RESOURCE where NAME in (" + for ctr, ignore_name in enumerate(names): + if ctr != 0: + statement += ", " + statement += ":%s" % (ctr,) + statement += ")" + results = self._db_values_for_sql(statement, *names) + return results + + def searchValid(self, filter): + if isinstance(filter, caldavxml.Filter): + qualifiers = calendarquery.sqlcalendarquery(filter) + else: + qualifiers = None + + return qualifiers is not None + def search(self, filter): """ Finds resources matching the given qualifiers. @@ -525,12 +550,14 @@ instances = calendar.expandTimeRanges(expand_max) for key in instances: instance = instances[key] + start = instance.start.replace(tzinfo=utc) + end = instance.end.replace(tzinfo=utc) float = ('N', 'Y')[instance.start.tzinfo is None] self._db_execute( """ insert into TIMESPAN (NAME, FLOAT, START, END) values (:1, :2, :3, :4) - """, name, float, normalizeForIndex(instance.start), normalizeForIndex(instance.end) + """, name, float, start, end ) self._db_execute( Modified: CalendarServer/trunk/twistedcaldav/method/report_calquery.py =================================================================== --- CalendarServer/trunk/twistedcaldav/method/report_calquery.py 2007-04-03 19:49:36 UTC (rev 1445) +++ CalendarServer/trunk/twistedcaldav/method/report_calquery.py 2007-04-04 14:46:26 UTC (rev 1446) @@ -71,15 +71,17 @@ if query.qname() == ("DAV:", "allprop"): propertiesForResource = report_common.allPropertiesForResource + generate_calendar_data = False elif query.qname() == ("DAV:", "propname"): propertiesForResource = report_common.propertyNamesForResource + generate_calendar_data = False elif query.qname() == ("DAV:", "prop"): propertiesForResource = report_common.propertyListForResource # Verify that any calendar-data element matches what we can handle - result, message = report_common.validPropertyListCalendarDataTypeVersion(query) + result, message, generate_calendar_data = report_common.validPropertyListCalendarDataTypeVersion(query) if not result: log.err(message) raise HTTPError(ErrorResponse(responsecode.FORBIDDEN, (caldav_namespace, "supported-calendar-data"))) @@ -101,7 +103,7 @@ @param uri: the uri for the calendar collecton resource. """ - def queryCalendarObjectResource(resource, uri, name, calendar): + def queryCalendarObjectResource(resource, uri, name, calendar, query_ok = False): """ Run a query on the specified calendar. @param resource: the L{CalDAVFile} for the calendar. @@ -110,7 +112,7 @@ @param calendar: the L{Component} calendar read from the resource. """ - if filter.match(calendar): + if query_ok or filter.match(calendar): # Check size of results is within limit matchcount[0] += 1 if matchcount[0] > max_number_of_matches: @@ -146,23 +148,37 @@ # Check for disabled access if filteredaces is not None: - for name, uid, type in calresource.index().search(filter): #@UnusedVariable - # Check privileges - must have at least DAV:read - child = waitForDeferred(request.locateChildResource(calresource, name)) - yield child - child = child.getResult() - - try: - d = waitForDeferred(child.checkPrivileges(request, (davxml.Read(),), inherited_aces=filteredaces)) - yield d - d.getResult() - except: - continue - - calendar = calresource.iCalendar(name) - assert calendar is not None, "Calendar %s is missing from calendar collection %r" % (name, self) + # See whether the filter is valid for an index only query + index_query_ok = calresource.index().searchValid(filter) + + # Get list of children that match the search and have read access + names = [name for name, ignore_uid, ignore_type in calresource.index().search(filter)] + + # Now determine which valid resources are readable and which are not + ok_resources = [] + d = calresource.findChildrenFaster( + "1", + request, + lambda x, y: ok_resources.append((x, y)), + None, + names, + (davxml.Read(),), + inherited_aces=filteredaces + ) + x = waitForDeferred(d) + yield x + x.getResult() + + for child, child_uri in ok_resources: + child_name = child_uri[child_uri.rfind("/") + 1:] - d = waitForDeferred(queryCalendarObjectResource(child, uri, name, calendar)) + if generate_calendar_data or not index_query_ok: + calendar = calresource.iCalendar(child_name) + assert calendar is not None, "Calendar %s is missing from calendar collection %r" % (child_name, self) + else: + calendar = None + + d = waitForDeferred(queryCalendarObjectResource(child, uri, child_name, calendar, query_ok = index_query_ok)) yield d d.getResult() else: Modified: CalendarServer/trunk/twistedcaldav/method/report_common.py =================================================================== --- CalendarServer/trunk/twistedcaldav/method/report_common.py 2007-04-03 19:49:36 UTC (rev 1445) +++ CalendarServer/trunk/twistedcaldav/method/report_common.py 2007-04-04 14:46:26 UTC (rev 1446) @@ -193,14 +193,16 @@ result = True message = "" + generate_calendar_data = False for property in prop.children: if isinstance(property, caldavxml.CalendarData): if not property.verifyTypeVersion([("text/calendar", "2.0")]): result = False message = "Calendar-data element type/version not supported: content-type: %s, version: %s" % (property.content_type,property.version) + generate_calendar_data = True break - return result, message + return result, message, generate_calendar_data def _namedPropertiesForResource(request, props, resource, calendar=None): """ Modified: CalendarServer/trunk/twistedcaldav/method/report_multiget.py =================================================================== --- CalendarServer/trunk/twistedcaldav/method/report_multiget.py 2007-04-03 19:49:36 UTC (rev 1445) +++ CalendarServer/trunk/twistedcaldav/method/report_multiget.py 2007-04-04 14:46:26 UTC (rev 1446) @@ -28,6 +28,7 @@ from twisted.web2.dav import davxml from twisted.web2.dav.element.base import dav_namespace from twisted.web2.dav.http import ErrorResponse, MultiStatusResponse +from twisted.web2.dav.util import joinURL from twisted.web2.http import HTTPError, StatusResponse from twistedcaldav.caldavxml import caldav_namespace @@ -63,15 +64,17 @@ if propertyreq.qname() == ("DAV:", "allprop"): propertiesForResource = report_common.allPropertiesForResource + generate_calendar_data = False elif propertyreq.qname() == ("DAV:", "propname"): propertiesForResource = report_common.propertyNamesForResource + generate_calendar_data = False elif propertyreq.qname() == ("DAV:", "prop"): propertiesForResource = report_common.propertyListForResource # Verify that any calendar-data element matches what we can handle - result, message = report_common.validPropertyListCalendarDataTypeVersion(propertyreq) + result, message, generate_calendar_data = report_common.validPropertyListCalendarDataTypeVersion(propertyreq) if not result: log.err(message) raise HTTPError(ErrorResponse(responsecode.FORBIDDEN, (caldav_namespace, "supported-calendar-data"))) @@ -121,101 +124,147 @@ filteredaces = None if not disabled: - for href in resources: - - resource_uri = str(href) - - # Do href checks - if requestURIis == "calendar": - # Verify that href is an immediate child of the request URI and that resource exists. + + def doCalendarResponse(): + # Verify that requested resources are immediate children of the request-URI + valid_names = [] + for href in resources: + resource_uri = str(href) name = unquote(resource_uri[resource_uri.rfind("/") + 1:]) if not self._isChildURI(request, resource_uri) or self.getChild(name) is None: responses.append(davxml.StatusResponse(href, davxml.Status.fromResponseCode(responsecode.NOT_FOUND))) - continue - - # Verify that we are dealing with a calendar object resource - if not self.index().resourceExists(name): + else: + valid_names.append(name) + if not valid_names: + yield None + return + + # Verify that valid requested resources are calendar objects + exists_names = tuple(self.index().resourcesExist(valid_names)) + checked_names = [] + for name in valid_names: + if name not in exists_names: + href = davxml.HRef.fromString(joinURL(request.uri, name)) responses.append(davxml.StatusResponse(href, davxml.Status.fromResponseCode(responsecode.NOT_ALLOWED))) - continue - - child = waitForDeferred(request.locateResource(resource_uri)) - yield child - child = child.getResult() + else: + checked_names.append(name) + + # Now determine which valid resources are readable and which are not + ok_resources = [] + bad_resources = [] + d = self.findChildrenFaster( + "1", + request, + lambda x, y: ok_resources.append((x, y)), + lambda x, y: bad_resources.append((x, y)), + checked_names, + (davxml.Read(),), + inherited_aces=filteredaces + ) + x = waitForDeferred(d) + yield x + x.getResult() + + # Get properties for all valid readable resources + for resource, href in ok_resources: + d = waitForDeferred(report_common.responseForHref(request, responses, davxml.HRef.fromString(href), resource, None, propertiesForResource, propertyreq)) + yield d + d.getResult() - elif requestURIis == "collection": - name = unquote(resource_uri[resource_uri.rfind("/") + 1:]) - if not self._isChildURI(request, resource_uri, False): - responses.append(davxml.StatusResponse(href, davxml.Status.fromResponseCode(responsecode.NOT_FOUND))) - continue - - child = waitForDeferred(request.locateResource(resource_uri)) - yield child - child = child.getResult() + # Indicate error for all valid non-readable resources + for ignore_resource, href in bad_resources: + responses.append(davxml.StatusResponse(davxml.HRef.fromString(href), davxml.Status.fromResponseCode(responsecode.NOT_ALLOWED))) + + doCalendarResponse = deferredGenerator(doCalendarResponse) - if not child or not child.exists(): - responses.append(davxml.StatusResponse(href, davxml.Status.fromResponseCode(responsecode.NOT_FOUND))) - continue - - parent = waitForDeferred(child.locateParent(request, resource_uri)) - yield parent - parent = parent.getResult() - - if not parent.isCalendarCollection() or not parent.index().resourceExists(name): - responses.append(davxml.StatusResponse(href, davxml.Status.fromResponseCode(responsecode.NOT_ALLOWED))) - continue + if requestURIis == "calendar": + d = waitForDeferred(doCalendarResponse()) + yield d + d.getResult() + else: + for href in resources: + + resource_uri = str(href) + + # Do href checks + if requestURIis == "calendar": + pass + + # TODO: we can optimize this one in a similar manner to the calendar case + elif requestURIis == "collection": + name = unquote(resource_uri[resource_uri.rfind("/") + 1:]) + if not self._isChildURI(request, resource_uri, False): + responses.append(davxml.StatusResponse(href, davxml.Status.fromResponseCode(responsecode.NOT_FOUND))) + continue + + child = waitForDeferred(request.locateResource(resource_uri)) + yield child + child = child.getResult() + + if not child or not child.exists(): + responses.append(davxml.StatusResponse(href, davxml.Status.fromResponseCode(responsecode.NOT_FOUND))) + continue + + parent = waitForDeferred(child.locateParent(request, resource_uri)) + yield parent + parent = parent.getResult() + + if not parent.isCalendarCollection() or not parent.index().resourceExists(name): + responses.append(davxml.StatusResponse(href, davxml.Status.fromResponseCode(responsecode.NOT_ALLOWED))) + continue + + # Check privileges on parent - must have at least DAV:read + try: + d = waitForDeferred(parent.checkPrivileges(request, (davxml.Read(),))) + yield d + d.getResult() + except: + responses.append(davxml.StatusResponse(href, davxml.Status.fromResponseCode(responsecode.NOT_ALLOWED))) + continue + + # Cache the last parent's inherited aces for checkPrivileges optimization + if lastParent != parent: + lastParent = parent - # Check privileges on parent - must have at least DAV:read - try: - d = waitForDeferred(parent.checkPrivileges(request, (davxml.Read(),))) - yield d - d.getResult() - except: - responses.append(davxml.StatusResponse(href, davxml.Status.fromResponseCode(responsecode.NOT_ALLOWED))) - continue - - # Cache the last parent's inherited aces for checkPrivileges optimization - if lastParent != parent: - lastParent = parent + # Do some optimisation of access control calculation by determining any inherited ACLs outside of + # the child resource loop and supply those to the checkPrivileges on each child. + filteredaces = waitForDeferred(parent.inheritedACEsforChildren(request)) + yield filteredaces + filteredaces = filteredaces.getResult() + + else: + name = unquote(resource_uri[resource_uri.rfind("/") + 1:]) + if (resource_uri != request.uri) or not self.exists(): + responses.append(davxml.StatusResponse(href, davxml.Status.fromResponseCode(responsecode.NOT_FOUND))) + continue + + parent = waitForDeferred(self.locateParent(request, resource_uri)) + yield parent + parent = parent.getResult() + + if not parent.isPseudoCalendarCollection() or not parent.index().resourceExists(name): + responses.append(davxml.StatusResponse(href, davxml.Status.fromResponseCode(responsecode.NOT_ALLOWED))) + continue + child = self # Do some optimisation of access control calculation by determining any inherited ACLs outside of # the child resource loop and supply those to the checkPrivileges on each child. filteredaces = waitForDeferred(parent.inheritedACEsforChildren(request)) yield filteredaces filteredaces = filteredaces.getResult() - - else: - name = unquote(resource_uri[resource_uri.rfind("/") + 1:]) - if (resource_uri != request.uri) or not self.exists(): - responses.append(davxml.StatusResponse(href, davxml.Status.fromResponseCode(responsecode.NOT_FOUND))) - continue - - parent = waitForDeferred(self.locateParent(request, resource_uri)) - yield parent - parent = parent.getResult() - - if not parent.isPseudoCalendarCollection() or not parent.index().resourceExists(name): + + # Check privileges - must have at least DAV:read + try: + d = waitForDeferred(child.checkPrivileges(request, (davxml.Read(),), inherited_aces=filteredaces)) + yield d + d.getResult() + except: responses.append(davxml.StatusResponse(href, davxml.Status.fromResponseCode(responsecode.NOT_ALLOWED))) continue - child = self - # Do some optimisation of access control calculation by determining any inherited ACLs outside of - # the child resource loop and supply those to the checkPrivileges on each child. - filteredaces = waitForDeferred(parent.inheritedACEsforChildren(request)) - yield filteredaces - filteredaces = filteredaces.getResult() - - # Check privileges - must have at least DAV:read - try: - d = waitForDeferred(child.checkPrivileges(request, (davxml.Read(),), inherited_aces=filteredaces)) + d = waitForDeferred(report_common.responseForHref(request, responses, href, child, None, propertiesForResource, propertyreq)) yield d d.getResult() - except: - responses.append(davxml.StatusResponse(href, davxml.Status.fromResponseCode(responsecode.NOT_ALLOWED))) - continue - - d = waitForDeferred(report_common.responseForHref(request, responses, href, child, None, propertiesForResource, propertyreq)) - yield d - d.getResult() yield MultiStatusResponse(responses)