blob: 6ffc154a075c58da6f8a64c63d8438579d41dda2 [file] [log] [blame]
// Copyright 2020 The LUCI Authors.
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// See the License for the specific language governing permissions and
// limitations under the License.
// Package realmset provides queryable representation of LUCI Realms DB.
// Used internally by authdb.Snapshot.
package realmset
import (
// ExpectedAPIVersion is the supported value of api_version field.
// See Build implementation for details.
const ExpectedAPIVersion = 1
// Realms is a queryable representation of realms.Realms proto.
type Realms struct {
perms map[string]PermissionIndex // permission name -> its index
names stringset.Set // just names of all defined realms
realms map[realmAndPerm]groupsAndIdents // <realm, perm> -> who has it
data map[string]*protocol.RealmData // per-realm attached RealmData
// PermissionIndex is used in place of permission names.
// Note: should match an int type used in `permissions` field in the proto.
type PermissionIndex uint32
// realmAndPerm is used as a composite key in `realms` map.
type realmAndPerm struct {
realm string
perm PermissionIndex
// groupsAndIdents is used as a value in `realms` map.
type groupsAndIdents struct {
groups graph.SortedNodeSet
idents stringset.Set
// PermissionIndex returns an index of the given permission.
// It can be passed to QueryAuthorized. Returns (0, false) if there's no such
// permission in the Realms DB.
func (r *Realms) PermissionIndex(perm realms.Permission) (idx PermissionIndex, ok bool) {
idx, ok = r.perms[perm.Name()]
// HasRealm returns true if the given realm exists in the DB.
func (r *Realms) HasRealm(realm string) bool {
return r.names.Has(realm)
// Data returns RealmData attached to a realm or nil if none.
func (r *Realms) Data(realm string) *protocol.RealmData {
// QueryAuthorized returns a representation of principals that have the
// requested permission in the given realm.
// The permission should be given as its index obtained via PermissionIndex.
// The realm name is not validated. Unknown or invalid realms are silently
// treated as empty. No fallback to @root happens.
// Returns a set of groups with principals that have the permission and a set
// of identity strings that were specified in the realm ACL directly (not via
// a group). nils are used in place of empty sets.
// The set of groups is represented by a sorted slice of group indexes in a
// graph.QueryableGraph which was passed to Build().
func (r *Realms) QueryAuthorized(realm string, perm PermissionIndex) (graph.SortedNodeSet, stringset.Set) {
out := r.realms[realmAndPerm{realm, perm}]
return out.groups, out.idents
// Build constructs Realms from the proto message and the group graph.
func Build(r *protocol.Realms, qg *graph.QueryableGraph) (*Realms, error) {
// Do not use realms.Realms we don't understand. Better to go offline
// completely than mistakenly allow access to something private by
// misinterpreting realm rules (e.g. if a new hypothetical DENY rule is
// misinterpreted as ALLOW).
// Bumping `api_version` (if it ever happens) should be done extremely
// carefully in multiple stages:
// 1. Update components.auth to understand both new and old api_version.
// 2. Redeploy *everything*.
// 3. Update Auth Service to generate realms.Realms using the new API.
if r.ApiVersion != ExpectedAPIVersion {
return nil, errors.Reason(
"Realms proto has api_version %d not compatible with this service (it expects %d)",
r.ApiVersion, ExpectedAPIVersion).Err()
// Build map: permission name -> its index (since Binding messages operate
// with indexes). Using ints as keys is also slightly faster than strings.
perms := make(map[string]PermissionIndex, len(r.Permissions))
for idx, perm := range r.Permissions {
perms[perm.Name] = PermissionIndex(idx)
// Gather names of all realms for HasRealm check.
names := stringset.New(len(r.Realms))
for _, realm := range r.Realms {
// This is the `realms` map under construction. We'll shrink its memory
// footprint at the end. Just like `realms` it uses a composite key
// realmAndPerm as a more memory-efficient alternative to a map of maps
// (realm -> perm -> principals).
type principalSet struct {
groups graph.NodeSet
idents stringset.Set
realmsToBe := map[realmAndPerm]principalSet{}
// interner is used to deduplicate memory used to store identity names.
interner := stringInterner{}
// Visit all bindings in all realms and update principal sets in realmsToBe.
for _, realm := range r.Realms {
for _, binding := range realm.Bindings {
// Categorize 'principals' into groups and identity strings.
groups, idents := categorizePrincipals(binding.Principals, qg, interner)
// Add them into the corresponding principal sets in realmsToBe.
for _, permIdx := range binding.Permissions {
key := realmAndPerm{realm.Name, PermissionIndex(permIdx)}
ps, ok := realmsToBe[key]
if !ok {
ps = principalSet{
groups: make(graph.NodeSet, len(groups)),
idents: stringset.New(len(idents)),
realmsToBe[key] = ps
for _, idx := range groups {
for _, ident := range idents {
// Replace identically looking group sets with references to a single copy.
// Also throw away zero-length sets, just a waste of memory. Finally, for
// identity sets we just keep using stringset.Set we've built as is, assuming
// using identities in Realm ACLs directly is rare and not worth optimizing
// for (on top of the string interning optimization we've already done).
realms := make(map[realmAndPerm]groupsAndIdents, len(realmsToBe))
dedupper := graph.NodeSetDedupper{}
for key, sets := range realmsToBe {
var groups graph.SortedNodeSet
if len(sets.groups) > 0 {
groups = dedupper.Dedup(sets.groups)
var idents stringset.Set
if sets.idents.Len() > 0 {
idents = sets.idents
realms[key] = groupsAndIdents{groups: groups, idents: idents}
// Extract attached per-realm data into a queryable map.
count := 0
for _, realm := range r.Realms {
if realm.Data != nil {
data := make(map[string]*protocol.RealmData, count)
for _, realm := range r.Realms {
if realm.Data != nil {
data[realm.Name] = realm.Data
return &Realms{
perms: perms,
names: names,
realms: realms,
data: data,
}, nil
// stringInterner implements string interning to save some memory.
type stringInterner map[string]string
// intern returns an interned copy of 's'.
func (si stringInterner) intern(s string) string {
if existing, ok := si[s]; ok {
return existing
si[s] = s
return s
// categorizePrincipals splits a list of principals into a list of groups
// (identified by their indexes in a QueryableGraph) and list of identity names.
// Unknown groups are silently skipped.
func categorizePrincipals(p []string, qg *graph.QueryableGraph, interner stringInterner) (groups []graph.NodeIndex, idents []string) {
for _, principal := range p {
if strings.HasPrefix(principal, "group:") {
if idx, ok := qg.GroupIndex(strings.TrimPrefix(principal, "group:")); ok {
groups = append(groups, idx)
} else {
idents = append(idents, interner.intern(principal))