public inbox for [email protected]help / color / mirror / Atom feed
[PATCH 2/2] make LogwrtResult atomic 3+ messages / 2 participants [nested] [flat]
* [PATCH 2/2] make LogwrtResult atomic @ 2021-02-02 17:03 Alvaro Herrera <[email protected]> 0 siblings, 0 replies; 3+ messages in thread From: Alvaro Herrera @ 2021-02-02 17:03 UTC (permalink / raw) --- src/backend/access/transam/xlog.c | 66 +++++++++++++++---------------- 1 file changed, 32 insertions(+), 34 deletions(-) diff --git a/src/backend/access/transam/xlog.c b/src/backend/access/transam/xlog.c index f03bd473e2..10802bd56f 100644 --- a/src/backend/access/transam/xlog.c +++ b/src/backend/access/transam/xlog.c @@ -405,12 +405,9 @@ static XLogRecPtr RedoStartLSN = InvalidXLogRecPtr; * These structs are identical but are declared separately to indicate their * slightly different functions. * - * To read XLogCtl->LogwrtResult, you must hold either info_lck or - * WALWriteLock. To update it, you need to hold both locks. The point of - * this arrangement is that the value can be examined by code that already - * holds WALWriteLock without needing to grab info_lck as well. In addition - * to the shared variable, each backend has a private copy of LogwrtResult, - * which is updated when convenient. + * XLogCtl->LogwrtResult is read and written using atomic operations. + * In addition to the shared variable, each backend has a private copy of + * LogwrtResult, each member of which is separately updated when convenient. * * The request bookkeeping is simpler: there is a shared XLogCtl->LogwrtRqst * (protected by info_lck), but we don't need to cache any copies of it. @@ -433,6 +430,12 @@ static XLogRecPtr RedoStartLSN = InvalidXLogRecPtr; *---------- */ +typedef struct XLogwrtAtomic +{ + pg_atomic_uint64 Write; /* last byte + 1 of write position */ + pg_atomic_uint64 Flush; /* last byte + 1 of flush position */ +} XLogwrtAtomic; + typedef struct XLogwrtRqst { XLogRecPtr Write; /* last byte + 1 to write out */ @@ -596,6 +599,7 @@ typedef struct XLogCtlData { XLogCtlInsert Insert; + XLogwrtAtomic LogwrtResult; /* Protected by info_lck: */ XLogwrtRqst LogwrtRqst; XLogRecPtr RedoRecPtr; /* a recent copy of Insert->RedoRecPtr */ @@ -613,12 +617,6 @@ typedef struct XLogCtlData pg_time_t lastSegSwitchTime; XLogRecPtr lastSegSwitchLSN; - /* - * Protected by info_lck and WALWriteLock (you must hold either lock to - * read it, but both to update) - */ - XLogwrtResult LogwrtResult; - /* * Latest initialized page in the cache (last byte position + 1). * @@ -1172,9 +1170,10 @@ XLogInsertRecord(XLogRecData *rdata, /* advance global request to include new block(s) */ if (XLogCtl->LogwrtRqst.Write < EndPos) XLogCtl->LogwrtRqst.Write = EndPos; - /* update local result copy while I have the chance */ - LogwrtResult = XLogCtl->LogwrtResult; SpinLockRelease(&XLogCtl->info_lck); + /* update local result copy */ + LogwrtResult.Write = pg_atomic_read_u64(&XLogCtl->LogwrtResult.Write); + LogwrtResult.Flush = pg_atomic_read_u64(&XLogCtl->LogwrtResult.Flush); } /* @@ -2170,13 +2169,13 @@ AdvanceXLInsertBuffer(XLogRecPtr upto, bool opportunistic) SpinLockAcquire(&XLogCtl->info_lck); if (XLogCtl->LogwrtRqst.Write < OldPageRqstPtr) XLogCtl->LogwrtRqst.Write = OldPageRqstPtr; - LogwrtResult = XLogCtl->LogwrtResult; SpinLockRelease(&XLogCtl->info_lck); /* * Now that we have an up-to-date LogwrtResult value, see if we * still need to write it or if someone else already did. */ + LogwrtResult.Write = pg_atomic_read_u64(&XLogCtl->LogwrtResult.Write); if (LogwrtResult.Write < OldPageRqstPtr) { /* @@ -2191,7 +2190,7 @@ AdvanceXLInsertBuffer(XLogRecPtr upto, bool opportunistic) LWLockAcquire(WALWriteLock, LW_EXCLUSIVE); - LogwrtResult = XLogCtl->LogwrtResult; + LogwrtResult.Write = pg_atomic_read_u64(&XLogCtl->LogwrtResult.Write); if (LogwrtResult.Write >= OldPageRqstPtr) { /* OK, someone wrote it already */ @@ -2438,7 +2437,7 @@ XLogWrite(XLogwrtRqst WriteRqst, bool flexible) /* * Update local LogwrtResult (caller probably did this already, but...) */ - LogwrtResult = XLogCtl->LogwrtResult; + LogwrtResult.Write = pg_atomic_read_u64(&XLogCtl->LogwrtResult.Write); /* * Since successive pages in the xlog cache are consecutively allocated, @@ -2636,7 +2635,6 @@ XLogWrite(XLogwrtRqst WriteRqst, bool flexible) */ if (LogwrtResult.Flush < WriteRqst.Flush && LogwrtResult.Flush < LogwrtResult.Write) - { /* * Could get here without iterating above loop, in which case we might @@ -2675,8 +2673,10 @@ XLogWrite(XLogwrtRqst WriteRqst, bool flexible) * code in a couple of places. */ { + pg_atomic_monotonic_advance_u64(&XLogCtl->LogwrtResult.Write, LogwrtResult.Write); + pg_atomic_monotonic_advance_u64(&XLogCtl->LogwrtResult.Flush, LogwrtResult.Flush); + pg_memory_barrier(); SpinLockAcquire(&XLogCtl->info_lck); - XLogCtl->LogwrtResult = LogwrtResult; if (XLogCtl->LogwrtRqst.Write < LogwrtResult.Write) XLogCtl->LogwrtRqst.Write = LogwrtResult.Write; if (XLogCtl->LogwrtRqst.Flush < LogwrtResult.Flush) @@ -2696,8 +2696,8 @@ XLogSetAsyncXactLSN(XLogRecPtr asyncXactLSN) XLogRecPtr WriteRqstPtr = asyncXactLSN; bool sleeping; + LogwrtResult.Flush = pg_atomic_read_u64(&XLogCtl->LogwrtResult.Flush); SpinLockAcquire(&XLogCtl->info_lck); - LogwrtResult = XLogCtl->LogwrtResult; sleeping = XLogCtl->WalWriterSleeping; if (XLogCtl->asyncXactLSN < asyncXactLSN) XLogCtl->asyncXactLSN = asyncXactLSN; @@ -2908,10 +2908,10 @@ XLogFlush(XLogRecPtr record) SpinLockAcquire(&XLogCtl->info_lck); if (WriteRqstPtr < XLogCtl->LogwrtRqst.Write) WriteRqstPtr = XLogCtl->LogwrtRqst.Write; - LogwrtResult = XLogCtl->LogwrtResult; SpinLockRelease(&XLogCtl->info_lck); /* done already? */ + LogwrtResult.Flush = pg_atomic_read_u64(&XLogCtl->LogwrtResult.Flush); if (record <= LogwrtResult.Flush) break; @@ -2939,7 +2939,7 @@ XLogFlush(XLogRecPtr record) } /* Got the lock; recheck whether request is satisfied */ - LogwrtResult = XLogCtl->LogwrtResult; + LogwrtResult.Flush = pg_atomic_read_u64(&XLogCtl->LogwrtResult.Flush); if (record <= LogwrtResult.Flush) { LWLockRelease(WALWriteLock); @@ -3056,7 +3056,6 @@ XLogBackgroundFlush(void) /* read LogwrtResult and update local state */ SpinLockAcquire(&XLogCtl->info_lck); - LogwrtResult = XLogCtl->LogwrtResult; WriteRqst = XLogCtl->LogwrtRqst; SpinLockRelease(&XLogCtl->info_lck); @@ -3064,8 +3063,10 @@ XLogBackgroundFlush(void) WriteRqst.Write -= WriteRqst.Write % XLOG_BLCKSZ; /* if we have already flushed that far, consider async commit records */ + LogwrtResult.Flush = pg_atomic_read_u64(&XLogCtl->LogwrtResult.Flush); if (WriteRqst.Write <= LogwrtResult.Flush) { + pg_memory_barrier(); SpinLockAcquire(&XLogCtl->info_lck); WriteRqst.Write = XLogCtl->asyncXactLSN; SpinLockRelease(&XLogCtl->info_lck); @@ -3081,6 +3082,7 @@ XLogBackgroundFlush(void) { if (openLogFile >= 0) { + LogwrtResult.Write = pg_atomic_read_u64(&XLogCtl->LogwrtResult.Write); if (!XLByteInPrevSeg(LogwrtResult.Write, openLogSegNo, wal_segment_size)) { @@ -3140,7 +3142,8 @@ XLogBackgroundFlush(void) /* now wait for any in-progress insertions to finish and get write lock */ WaitXLogInsertionsToFinish(WriteRqst.Write); LWLockAcquire(WALWriteLock, LW_EXCLUSIVE); - LogwrtResult = XLogCtl->LogwrtResult; + LogwrtResult.Write = pg_atomic_read_u64(&XLogCtl->LogwrtResult.Write); + LogwrtResult.Flush = pg_atomic_read_u64(&XLogCtl->LogwrtResult.Flush); if (WriteRqst.Write > LogwrtResult.Write || WriteRqst.Flush > LogwrtResult.Flush) { @@ -3228,9 +3231,7 @@ XLogNeedsFlush(XLogRecPtr record) return false; /* read LogwrtResult and update local state */ - SpinLockAcquire(&XLogCtl->info_lck); - LogwrtResult = XLogCtl->LogwrtResult; - SpinLockRelease(&XLogCtl->info_lck); + LogwrtResult.Flush = pg_atomic_read_u64(&XLogCtl->LogwrtResult.Flush); /* check again */ if (record <= LogwrtResult.Flush) @@ -7779,7 +7780,8 @@ StartupXLOG(void) LogwrtResult.Write = LogwrtResult.Flush = EndOfLog; - XLogCtl->LogwrtResult = LogwrtResult; + pg_atomic_write_u64(&XLogCtl->LogwrtResult.Write, EndOfLog); + pg_atomic_write_u64(&XLogCtl->LogwrtResult.Flush, EndOfLog); XLogCtl->LogwrtRqst.Write = EndOfLog; XLogCtl->LogwrtRqst.Flush = EndOfLog; @@ -8498,9 +8500,7 @@ GetInsertRecPtr(void) XLogRecPtr GetFlushRecPtr(void) { - SpinLockAcquire(&XLogCtl->info_lck); - LogwrtResult = XLogCtl->LogwrtResult; - SpinLockRelease(&XLogCtl->info_lck); + LogwrtResult.Flush = pg_atomic_read_u64(&XLogCtl->LogwrtResult.Flush); return LogwrtResult.Flush; } @@ -11649,9 +11649,7 @@ GetXLogInsertRecPtr(void) XLogRecPtr GetXLogWriteRecPtr(void) { - SpinLockAcquire(&XLogCtl->info_lck); - LogwrtResult = XLogCtl->LogwrtResult; - SpinLockRelease(&XLogCtl->info_lck); + LogwrtResult.Write = pg_atomic_read_u64(&XLogCtl->LogwrtResult.Write); return LogwrtResult.Write; } -- 2.20.1 --0OAP2g/MAC+5xKAE-- ^ permalink raw reply [nested|flat] 3+ messages in thread
* further improving roles_is_member_of() @ 2024-04-12 04:16 Nathan Bossart <[email protected]> 0 siblings, 1 reply; 3+ messages in thread From: Nathan Bossart @ 2024-04-12 04:16 UTC (permalink / raw) To: Tom Lane <[email protected]>; +Cc: [email protected]; alex work <[email protected]>; Robert Haas <[email protected]> (moved to a new thread) On Thu, Mar 21, 2024 at 04:31:45PM -0400, Tom Lane wrote: > I wrote: >> ... I still see the problematic GRANT taking ~250ms, compared >> to 5ms in v15. roles_is_member_of is clearly on the hook for that. > > Ah: looks like that is mainly the fault of the list_append_unique_oid > calls in roles_is_member_of. That's also an O(N^2) cost of course, > though with a much smaller constant factor. > > I don't think we have any really cheap way to de-duplicate the role > OIDs, especially seeing that it has to be done on-the-fly within the > collection loop, and the order of roles_list is at least potentially > interesting. Not sure how to make further progress without a lot of > work. I looked at this one again because I suspect these "thousands of roles" cases are going to continue to appear. Specifically, I tried to convert the cached roles lists to hash tables to avoid the list_member_oid linear searches. That actually was pretty easy to do. The most complicated part is juggling a couple of lists to keep track of the roles we need to iterate over in roles_is_member_of(). AFAICT the only catch is that select_best_grantor() seems to depend on the ordering of roles_list so that it prefers a "closer" role. To deal with that, I added a "depth" field to the entry struct that can be used as a tiebreaker. I'm not certain that this is good enough, though. As shown in the attached work-in-progress patch, this actually ends up removing more code than it adds, and it seems to provide similar results to HEAD (using the benchmark from the previous thread [0]). I intend to test it with many more roles to see if it's better in more extreme cases. [0] https://postgr.es/m/341186.1711037256%40sss.pgh.pa.us -- Nathan Bossart Amazon Web Services: https://aws.amazon.com Attachments: [text/x-diff] v1-0001-use-hash-tables-for-role-caches-work-in-progress.patch (13.3K, ../../20240412041633.GA2315447@nathanxps13/2-v1-0001-use-hash-tables-for-role-caches-work-in-progress.patch) download | inline diff: From 01fb5ac0d7394af6a3036011c33087b12f2809ce Mon Sep 17 00:00:00 2001 From: Nathan Bossart <[email protected]> Date: Thu, 11 Apr 2024 22:08:53 -0500 Subject: [PATCH v1 1/1] use hash tables for role caches (work in progress) --- src/backend/utils/adt/acl.c | 256 ++++++++++++++----------------- src/tools/pgindent/typedefs.list | 1 + 2 files changed, 113 insertions(+), 144 deletions(-) diff --git a/src/backend/utils/adt/acl.c b/src/backend/utils/adt/acl.c index dc10b4a483..d873ff8d13 100644 --- a/src/backend/utils/adt/acl.c +++ b/src/backend/utils/adt/acl.c @@ -55,6 +55,12 @@ typedef struct AclMode value; } priv_map; +typedef struct +{ + Oid role; + int depth; +} CachedRoleEntry; + /* * We frequently need to test whether a given role is a member of some other * role. In most of these tests the "given role" is the same, namely the @@ -76,17 +82,9 @@ enum RoleRecurseType ROLERECURSE_SETROLE = 2 /* recurse through grants with set_option */ }; static Oid cached_role[] = {InvalidOid, InvalidOid, InvalidOid}; -static List *cached_roles[] = {NIL, NIL, NIL}; +static HTAB *cached_roles[] = {NULL, NULL, NULL}; static uint32 cached_db_hash; -/* - * If the list of roles gathered by roles_is_member_of() grows larger than the - * below threshold, a Bloom filter is created to speed up list membership - * checks. This threshold is set arbitrarily high to avoid the overhead of - * creating the Bloom filter until it seems likely to provide a net benefit. - */ -#define ROLES_LIST_BLOOM_THRESHOLD 1024 - static const char *getid(const char *s, char *n, Node *escontext); static void putid(char *p, const char *s); static Acl *allocacl(int n); @@ -4926,53 +4924,6 @@ RoleMembershipCacheCallback(Datum arg, int cacheid, uint32 hashvalue) cached_role[ROLERECURSE_SETROLE] = InvalidOid; } -/* - * A helper function for roles_is_member_of() that provides an optimized - * implementation of list_append_unique_oid() via a Bloom filter. The caller - * (i.e., roles_is_member_of()) is responsible for freeing bf once it is done - * using this function. - */ -static inline List * -roles_list_append(List *roles_list, bloom_filter **bf, Oid role) -{ - unsigned char *roleptr = (unsigned char *) &role; - - /* - * If there is a previously-created Bloom filter, use it to try to - * determine whether the role is missing from the list. If it says yes, - * that's a hard fact and we can go ahead and add the role. If it says - * no, that's only probabilistic and we'd better search the list. Without - * a filter, we must always do an ordinary linear search through the - * existing list. - */ - if ((*bf && bloom_lacks_element(*bf, roleptr, sizeof(Oid))) || - !list_member_oid(roles_list, role)) - { - /* - * If the list is large, we take on the overhead of creating and - * populating a Bloom filter to speed up future calls to this - * function. - */ - if (*bf == NULL && - list_length(roles_list) > ROLES_LIST_BLOOM_THRESHOLD) - { - *bf = bloom_create(ROLES_LIST_BLOOM_THRESHOLD * 10, work_mem, 0); - foreach_oid(roleid, roles_list) - bloom_add_element(*bf, (unsigned char *) &roleid, sizeof(Oid)); - } - - /* - * Finally, add the role to the list and the Bloom filter, if it - * exists. - */ - roles_list = lappend_oid(roles_list, role); - if (*bf) - bloom_add_element(*bf, roleptr, sizeof(Oid)); - } - - return roles_list; -} - /* * Get a list of roles that the specified roleid is a member of * @@ -4992,16 +4943,16 @@ roles_list_append(List *roles_list, bloom_filter **bf, Oid role) * ADMIN OPTION on the role corresponding to admin_of, or to InvalidOid if * there is no such role. */ -static List * +static HTAB * roles_is_member_of(Oid roleid, enum RoleRecurseType type, Oid admin_of, Oid *admin_role) { Oid dba; - List *roles_list; - ListCell *l; - List *new_cached_roles; - MemoryContext oldctx; - bloom_filter *bf = NULL; + HTAB *roles_list; + List *curr_list; + HASHCTL ctl; + CachedRoleEntry *ent; + int depth = 0; Assert(OidIsValid(admin_of) == PointerIsValid(admin_role)); if (admin_role != NULL) @@ -5041,74 +4992,88 @@ roles_is_member_of(Oid roleid, enum RoleRecurseType type, * This is a bit tricky but works because the foreach() macro doesn't * fetch the next list element until the bottom of the loop. */ - roles_list = list_make1_oid(roleid); - - foreach(l, roles_list) + ctl.keysize = sizeof(Oid); + ctl.entrysize = sizeof(CachedRoleEntry); + roles_list = hash_create("roles list", 16, &ctl, HASH_ELEM | HASH_BLOBS); + ent = (CachedRoleEntry *) hash_search(roles_list, &roleid, HASH_ENTER, NULL); + ent->depth = depth; + curr_list = list_make1_oid(roleid); + + while (curr_list != NIL) { - Oid memberid = lfirst_oid(l); - CatCList *memlist; - int i; - - /* Find roles that memberid is directly a member of */ - memlist = SearchSysCacheList1(AUTHMEMMEMROLE, - ObjectIdGetDatum(memberid)); - for (i = 0; i < memlist->n_members; i++) + List *next_list = NIL; + bool found = false; + + depth++; + + foreach_oid(memberid, curr_list) { - HeapTuple tup = &memlist->members[i]->tuple; - Form_pg_auth_members form = (Form_pg_auth_members) GETSTRUCT(tup); - Oid otherid = form->roleid; - - /* - * While otherid==InvalidOid shouldn't appear in the catalog, the - * OidIsValid() avoids crashing if that arises. - */ - if (otherid == admin_of && form->admin_option && - OidIsValid(admin_of) && !OidIsValid(*admin_role)) - *admin_role = memberid; - - /* If we're supposed to ignore non-heritable grants, do so. */ - if (type == ROLERECURSE_PRIVS && !form->inherit_option) - continue; + CatCList *memlist; + int i; - /* If we're supposed to ignore non-SET grants, do so. */ - if (type == ROLERECURSE_SETROLE && !form->set_option) - continue; + /* Find roles that memberid is directly a member of */ + memlist = SearchSysCacheList1(AUTHMEMMEMROLE, + ObjectIdGetDatum(memberid)); + for (i = 0; i < memlist->n_members; i++) + { + HeapTuple tup = &memlist->members[i]->tuple; + Form_pg_auth_members form = (Form_pg_auth_members) GETSTRUCT(tup); + Oid otherid = form->roleid; + + /* + * While otherid==InvalidOid shouldn't appear in the catalog, + * the OidIsValid() avoids crashing if that arises. + */ + if (otherid == admin_of && form->admin_option && + OidIsValid(admin_of) && !OidIsValid(*admin_role)) + *admin_role = memberid; + + /* If we're supposed to ignore non-heritable grants, do so. */ + if (type == ROLERECURSE_PRIVS && !form->inherit_option) + continue; - /* - * Even though there shouldn't be any loops in the membership - * graph, we must test for having already seen this role. It is - * legal for instance to have both A->B and A->C->B. - */ - roles_list = roles_list_append(roles_list, &bf, otherid); - } - ReleaseSysCacheList(memlist); + /* If we're supposed to ignore non-SET grants, do so. */ + if (type == ROLERECURSE_SETROLE && !form->set_option) + continue; - /* implement pg_database_owner implicit membership */ - if (memberid == dba && OidIsValid(dba)) - roles_list = roles_list_append(roles_list, &bf, - ROLE_PG_DATABASE_OWNER); - } + /* + * Even though there shouldn't be any loops in the membership + * graph, we must test for having already seen this role. It + * is legal for instance to have both A->B and A->C->B. + */ + ent = (CachedRoleEntry *) hash_search(roles_list, &otherid, HASH_ENTER, &found); + if (!found) + { + ent->depth = depth; + next_list = lappend_oid(next_list, otherid); + } + } + ReleaseSysCacheList(memlist); - /* - * Free the Bloom filter created by roles_list_append(), if there is one. - */ - if (bf) - bloom_free(bf); + /* implement pg_database_owner implicit membership */ + if (memberid == dba && OidIsValid(dba)) + { + Oid dbowner = ROLE_PG_DATABASE_OWNER; - /* - * Copy the completed list into TopMemoryContext so it will persist. - */ - oldctx = MemoryContextSwitchTo(TopMemoryContext); - new_cached_roles = list_copy(roles_list); - MemoryContextSwitchTo(oldctx); - list_free(roles_list); + hash_search(roles_list, &dbowner, HASH_ENTER, &found); + if (!found) + { + ent->depth = depth; + next_list = lappend_oid(next_list, dbowner); + } + } + } + + list_free(curr_list); + curr_list = next_list; + } /* * Now safe to assign to state variable */ cached_role[type] = InvalidOid; /* just paranoia */ - list_free(cached_roles[type]); - cached_roles[type] = new_cached_roles; + hash_destroy(cached_roles[type]); + cached_roles[type] = roles_list; cached_role[type] = roleid; /* And now we can return the answer */ @@ -5127,6 +5092,8 @@ roles_is_member_of(Oid roleid, enum RoleRecurseType type, bool has_privs_of_role(Oid member, Oid role) { + HTAB *roles_list; + /* Fast path for simple case */ if (member == role) return true; @@ -5139,9 +5106,8 @@ has_privs_of_role(Oid member, Oid role) * Find all the roles that member has the privileges of, including * multi-level recursion, then see if target role is any one of them. */ - return list_member_oid(roles_is_member_of(member, ROLERECURSE_PRIVS, - InvalidOid, NULL), - role); + roles_list = roles_is_member_of(member, ROLERECURSE_PRIVS, InvalidOid, NULL); + return hash_search(roles_list, &role, HASH_FIND, NULL) != NULL; } /* @@ -5161,6 +5127,8 @@ has_privs_of_role(Oid member, Oid role) bool member_can_set_role(Oid member, Oid role) { + HTAB *roles_list; + /* Fast path for simple case */ if (member == role) return true; @@ -5173,9 +5141,8 @@ member_can_set_role(Oid member, Oid role) * Find all the roles that member can access via SET ROLE, including * multi-level recursion, then see if target role is any one of them. */ - return list_member_oid(roles_is_member_of(member, ROLERECURSE_SETROLE, - InvalidOid, NULL), - role); + roles_list = roles_is_member_of(member, ROLERECURSE_SETROLE, InvalidOid, NULL); + return hash_search(roles_list, &role, HASH_FIND, NULL) != NULL; } /* @@ -5207,6 +5174,8 @@ check_can_set_role(Oid member, Oid role) bool is_member_of_role(Oid member, Oid role) { + HTAB *roles_list; + /* Fast path for simple case */ if (member == role) return true; @@ -5219,9 +5188,8 @@ is_member_of_role(Oid member, Oid role) * Find all the roles that member is a member of, including multi-level * recursion, then see if target role is any one of them. */ - return list_member_oid(roles_is_member_of(member, ROLERECURSE_MEMBERS, - InvalidOid, NULL), - role); + roles_list = roles_is_member_of(member, ROLERECURSE_MEMBERS, InvalidOid, NULL); + return hash_search(roles_list, &role, HASH_FIND, NULL) != NULL; } /* @@ -5235,6 +5203,8 @@ is_member_of_role(Oid member, Oid role) bool is_member_of_role_nosuper(Oid member, Oid role) { + HTAB *roles_list; + /* Fast path for simple case */ if (member == role) return true; @@ -5243,9 +5213,8 @@ is_member_of_role_nosuper(Oid member, Oid role) * Find all the roles that member is a member of, including multi-level * recursion, then see if target role is any one of them. */ - return list_member_oid(roles_is_member_of(member, ROLERECURSE_MEMBERS, - InvalidOid, NULL), - role); + roles_list = roles_is_member_of(member, ROLERECURSE_MEMBERS, InvalidOid, NULL); + return hash_search(roles_list, &role, HASH_FIND, NULL) != NULL; } @@ -5340,9 +5309,11 @@ select_best_grantor(Oid roleId, AclMode privileges, Oid *grantorId, AclMode *grantOptions) { AclMode needed_goptions = ACL_GRANT_OPTION_FOR(privileges); - List *roles_list; + HTAB *roles_list; int nrights; - ListCell *l; + int best_depth = -1; + CachedRoleEntry *otherrole; + HASH_SEQ_STATUS status; /* * The object owner is always treated as having all grant options, so if @@ -5371,20 +5342,13 @@ select_best_grantor(Oid roleId, AclMode privileges, *grantOptions = ACL_NO_RIGHTS; nrights = 0; - foreach(l, roles_list) + hash_seq_init(&status, roles_list); + while ((otherrole = (CachedRoleEntry *) hash_seq_search(&status)) != NULL) { - Oid otherrole = lfirst_oid(l); AclMode otherprivs; - otherprivs = aclmask_direct(acl, otherrole, ownerId, + otherprivs = aclmask_direct(acl, otherrole->role, ownerId, needed_goptions, ACLMASK_ALL); - if (otherprivs == needed_goptions) - { - /* Found a suitable grantor */ - *grantorId = otherrole; - *grantOptions = otherprivs; - return; - } /* * If it has just some of the needed privileges, remember best @@ -5394,11 +5358,15 @@ select_best_grantor(Oid roleId, AclMode privileges, { int nnewrights = count_one_bits(otherprivs); - if (nnewrights > nrights) + if (nnewrights > nrights || + (nnewrights > 0 && + nnewrights == nrights && + otherrole->depth < best_depth)) { - *grantorId = otherrole; + *grantorId = otherrole->role; *grantOptions = otherprivs; nrights = nnewrights; + best_depth = otherrole->depth; } } } diff --git a/src/tools/pgindent/typedefs.list b/src/tools/pgindent/typedefs.list index cf05701c03..315023265a 100644 --- a/src/tools/pgindent/typedefs.list +++ b/src/tools/pgindent/typedefs.list @@ -362,6 +362,7 @@ CV CachedExpression CachedPlan CachedPlanSource +CachedRoleEntry CallContext CallStmt CancelRequestPacket -- 2.25.1 ^ permalink raw reply [nested|flat] 3+ messages in thread
* Re: further improving roles_is_member_of() @ 2024-04-12 19:19 Nathan Bossart <[email protected]> parent: Nathan Bossart <[email protected]> 0 siblings, 0 replies; 3+ messages in thread From: Nathan Bossart @ 2024-04-12 19:19 UTC (permalink / raw) To: Tom Lane <[email protected]>; +Cc: [email protected]; alex work <[email protected]>; Robert Haas <[email protected]> On Thu, Apr 11, 2024 at 11:16:33PM -0500, Nathan Bossart wrote: > As shown in the attached work-in-progress patch, this actually ends up > removing more code than it adds, and it seems to provide similar results to > HEAD (using the benchmark from the previous thread [0]). I intend to test > it with many more roles to see if it's better in more extreme cases. Even with 100K roles, the Bloom filter added in commit d365ae7 seems to do a pretty good job at keeping up with the hash table approach. The callers of roles_is_member_of() that do list_member_oid() on the returned list might benefit a little from a hash table, but I'm skeptical it makes much difference in practice. This was an interesting test, but I'll likely withdraw this patch shortly. -- Nathan Bossart Amazon Web Services: https://aws.amazon.com ^ permalink raw reply [nested|flat] 3+ messages in thread
end of thread, other threads:[~2024-04-12 19:19 UTC | newest] Thread overview: 3+ messages (download: mbox mbox.gz follow: Atom feed) -- links below jump to the message on this page -- 2021-02-02 17:03 [PATCH 2/2] make LogwrtResult atomic Alvaro Herrera <[email protected]> 2024-04-12 04:16 further improving roles_is_member_of() Nathan Bossart <[email protected]> 2024-04-12 19:19 ` Re: further improving roles_is_member_of() Nathan Bossart <[email protected]>
This inbox is served by agora; see mirroring instructions for how to clone and mirror all data and code used for this inbox