1// Copyright 2016 the Go-FUSE Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style
3// license that can be found in the LICENSE file.
4
5package nodefs
6
7import (
8	"log"
9	"sync"
10)
11
12// HandleMap translates objects in Go space to 64-bit handles that can
13// be given out to -say- the linux kernel as NodeIds.
14//
15// The 32 bits version of this is a threadsafe wrapper around a map.
16//
17// To use it, include "handled" as first member of the structure
18// you wish to export.
19//
20// This structure is thread-safe.
21type handleMap interface {
22	// Register stores "obj" and returns a unique (NodeId, generation) tuple.
23	Register(obj *handled) (handle, generation uint64)
24	Count() int
25	// Decode retrieves a stored object from its 64-bit handle.
26	Decode(uint64) *handled
27	// Forget decrements the reference counter for "handle" by "count" and drops
28	// the object if the refcount reaches zero.
29	// Returns a boolean whether the object was dropped and the object itself.
30	Forget(handle uint64, count int) (bool, *handled)
31	// Handle gets the object's NodeId.
32	Handle(obj *handled) uint64
33	// Has checks if NodeId is stored.
34	Has(uint64) bool
35}
36
37type handled struct {
38	handle     uint64
39	generation uint64
40	count      int
41}
42
43func (h *handled) verify() {
44	if h.count < 0 {
45		log.Panicf("negative lookup count %d", h.count)
46	}
47	if (h.count == 0) != (h.handle == 0) {
48		log.Panicf("registration mismatch: lookup %d id %d", h.count, h.handle)
49	}
50}
51
52const _ALREADY_MSG = "Object already has a handle"
53
54////////////////////////////////////////////////////////////////
55// portable version using 32 bit integers.
56
57type portableHandleMap struct {
58	sync.RWMutex
59	// The generation counter is incremented each time a NodeId is reused,
60	// hence the (NodeId, Generation) tuple is always unique.
61	generation uint64
62	// Number of currently used handles
63	used int
64	// Array of Go objects indexed by NodeId
65	handles []*handled
66	// Free slots in the "handles" array
67	freeIds []uint64
68}
69
70func newPortableHandleMap() *portableHandleMap {
71	return &portableHandleMap{
72		// Avoid handing out ID 0 and 1.
73		handles: []*handled{nil, nil},
74	}
75}
76
77func (m *portableHandleMap) Register(obj *handled) (handle, generation uint64) {
78	m.Lock()
79	defer m.Unlock()
80	// Reuse existing handle
81	if obj.count != 0 {
82		obj.count++
83		return obj.handle, obj.generation
84	}
85	// Create a new handle number or recycle one on from the free list
86	if len(m.freeIds) == 0 {
87		obj.handle = uint64(len(m.handles))
88		m.handles = append(m.handles, obj)
89	} else {
90		obj.handle = m.freeIds[len(m.freeIds)-1]
91		m.freeIds = m.freeIds[:len(m.freeIds)-1]
92		m.handles[obj.handle] = obj
93	}
94	// Increment generation number to guarantee the (handle, generation) tuple
95	// is unique
96	m.generation++
97	m.used++
98	obj.generation = m.generation
99	obj.count++
100
101	return obj.handle, obj.generation
102}
103
104func (m *portableHandleMap) Handle(obj *handled) (h uint64) {
105	m.RLock()
106	if obj.count == 0 {
107		h = 0
108	} else {
109		h = obj.handle
110	}
111	m.RUnlock()
112	return h
113}
114
115func (m *portableHandleMap) Count() int {
116	m.RLock()
117	c := m.used
118	m.RUnlock()
119	return c
120}
121
122func (m *portableHandleMap) Decode(h uint64) *handled {
123	m.RLock()
124	v := m.handles[h]
125	m.RUnlock()
126	return v
127}
128
129func (m *portableHandleMap) Forget(h uint64, count int) (forgotten bool, obj *handled) {
130	m.Lock()
131	obj = m.handles[h]
132	obj.count -= count
133	if obj.count < 0 {
134		log.Panicf("underflow: handle %d, count %d, object %d", h, count, obj.count)
135	} else if obj.count == 0 {
136		m.handles[h] = nil
137		m.freeIds = append(m.freeIds, h)
138		m.used--
139		forgotten = true
140		obj.handle = 0
141	}
142	m.Unlock()
143	return forgotten, obj
144}
145
146func (m *portableHandleMap) Has(h uint64) bool {
147	m.RLock()
148	ok := m.handles[h] != nil
149	m.RUnlock()
150	return ok
151}
152