|
36 | 36 | #include"common/hashfn.h" |
37 | 37 | #include"foreign/foreign.h" |
38 | 38 | #include"funcapi.h" |
| 39 | +#include"lib/bloomfilter.h" |
39 | 40 | #include"lib/qunique.h" |
40 | 41 | #include"miscadmin.h" |
41 | 42 | #include"utils/acl.h" |
@@ -78,6 +79,13 @@ static Oidcached_role[] = {InvalidOid, InvalidOid, InvalidOid}; |
78 | 79 | staticList*cached_roles[]= {NIL,NIL,NIL}; |
79 | 80 | staticuint32cached_db_hash; |
80 | 81 |
|
| 82 | +/* |
| 83 | + * If the list of roles gathered by roles_is_member_of() grows larger than the |
| 84 | + * below threshold, a Bloom filter is created to speed up list membership |
| 85 | + * checks. This threshold is set arbitrarily high to avoid the overhead of |
| 86 | + * creating the Bloom filter until it seems likely to provide a net benefit. |
| 87 | + */ |
| 88 | +#defineROLES_LIST_BLOOM_THRESHOLD 1024 |
81 | 89 |
|
82 | 90 | staticconstchar*getid(constchar*s,char*n,Node*escontext); |
83 | 91 | staticvoidputid(char*p,constchar*s); |
@@ -4918,6 +4926,53 @@ RoleMembershipCacheCallback(Datum arg, int cacheid, uint32 hashvalue) |
4918 | 4926 | cached_role[ROLERECURSE_SETROLE]=InvalidOid; |
4919 | 4927 | } |
4920 | 4928 |
|
| 4929 | +/* |
| 4930 | + * A helper function for roles_is_member_of() that provides an optimized |
| 4931 | + * implementation of list_append_unique_oid() via a Bloom filter. The caller |
| 4932 | + * (i.e., roles_is_member_of()) is responsible for freeing bf once it is done |
| 4933 | + * using this function. |
| 4934 | + */ |
| 4935 | +staticinlineList* |
| 4936 | +roles_list_append(List*roles_list,bloom_filter**bf,Oidrole) |
| 4937 | +{ |
| 4938 | +unsignedchar*roleptr= (unsignedchar*)&role; |
| 4939 | + |
| 4940 | +/* |
| 4941 | + * If there is a previously-created Bloom filter, use it to try to |
| 4942 | + * determine whether the role is missing from the list. If it says yes, |
| 4943 | + * that's a hard fact and we can go ahead and add the role. If it says |
| 4944 | + * no, that's only probabilistic and we'd better search the list. Without |
| 4945 | + * a filter, we must always do an ordinary linear search through the |
| 4946 | + * existing list. |
| 4947 | + */ |
| 4948 | +if ((*bf&&bloom_lacks_element(*bf,roleptr,sizeof(Oid)))|| |
| 4949 | +!list_member_oid(roles_list,role)) |
| 4950 | +{ |
| 4951 | +/* |
| 4952 | + * If the list is large, we take on the overhead of creating and |
| 4953 | + * populating a Bloom filter to speed up future calls to this |
| 4954 | + * function. |
| 4955 | + */ |
| 4956 | +if (*bf==NULL&& |
| 4957 | +list_length(roles_list)>ROLES_LIST_BLOOM_THRESHOLD) |
| 4958 | +{ |
| 4959 | +*bf=bloom_create(ROLES_LIST_BLOOM_THRESHOLD*10,work_mem,0); |
| 4960 | +foreach_oid(roleid,roles_list) |
| 4961 | +bloom_add_element(*bf, (unsignedchar*)&roleid,sizeof(Oid)); |
| 4962 | +} |
| 4963 | + |
| 4964 | +/* |
| 4965 | + * Finally, add the role to the list and the Bloom filter, if it |
| 4966 | + * exists. |
| 4967 | + */ |
| 4968 | +roles_list=lappend_oid(roles_list,role); |
| 4969 | +if (*bf) |
| 4970 | +bloom_add_element(*bf,roleptr,sizeof(Oid)); |
| 4971 | +} |
| 4972 | + |
| 4973 | +returnroles_list; |
| 4974 | +} |
| 4975 | + |
4921 | 4976 | /* |
4922 | 4977 | * Get a list of roles that the specified roleid is a member of |
4923 | 4978 | * |
@@ -4946,6 +5001,7 @@ roles_is_member_of(Oid roleid, enum RoleRecurseType type, |
4946 | 5001 | ListCell*l; |
4947 | 5002 | List*new_cached_roles; |
4948 | 5003 | MemoryContextoldctx; |
| 5004 | +bloom_filter*bf=NULL; |
4949 | 5005 |
|
4950 | 5006 | Assert(OidIsValid(admin_of)==PointerIsValid(admin_role)); |
4951 | 5007 | if (admin_role!=NULL) |
@@ -5023,16 +5079,22 @@ roles_is_member_of(Oid roleid, enum RoleRecurseType type, |
5023 | 5079 | * graph, we must test for having already seen this role. It is |
5024 | 5080 | * legal for instance to have both A->B and A->C->B. |
5025 | 5081 | */ |
5026 | | -roles_list=list_append_unique_oid(roles_list,otherid); |
| 5082 | +roles_list=roles_list_append(roles_list,&bf,otherid); |
5027 | 5083 | } |
5028 | 5084 | ReleaseSysCacheList(memlist); |
5029 | 5085 |
|
5030 | 5086 | /* implement pg_database_owner implicit membership */ |
5031 | 5087 | if (memberid==dba&&OidIsValid(dba)) |
5032 | | -roles_list=list_append_unique_oid(roles_list, |
5033 | | -ROLE_PG_DATABASE_OWNER); |
| 5088 | +roles_list=roles_list_append(roles_list,&bf, |
| 5089 | +ROLE_PG_DATABASE_OWNER); |
5034 | 5090 | } |
5035 | 5091 |
|
| 5092 | +/* |
| 5093 | + * Free the Bloom filter created by roles_list_append(), if there is one. |
| 5094 | + */ |
| 5095 | +if (bf) |
| 5096 | +bloom_free(bf); |
| 5097 | + |
5036 | 5098 | /* |
5037 | 5099 | * Copy the completed list into TopMemoryContext so it will persist. |
5038 | 5100 | */ |
|