ua_nodestore_hashmap.c 17 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537
  1. /* This work is licensed under a Creative Commons CCZero 1.0 Universal License.
  2. * See http://creativecommons.org/publicdomain/zero/1.0/ for more information.
  3. *
  4. * Copyright 2014-2019 (c) Fraunhofer IOSB (Author: Julius Pfrommer)
  5. * Copyright 2017 (c) Julian Grothoff
  6. * Copyright 2017 (c) Stefan Profanter, fortiss GmbH
  7. */
  8. #include <open62541/plugin/nodestore_default.h>
  9. #if UA_MULTITHREADING >= 100
  10. #define BEGIN_CRITSECT(NODEMAP) UA_LOCK(NODEMAP->lock)
  11. #define END_CRITSECT(NODEMAP) UA_UNLOCK(NODEMAP->lock)
  12. #else
  13. #define BEGIN_CRITSECT(NODEMAP) do {} while(0)
  14. #define END_CRITSECT(NODEMAP) do {} while(0)
  15. #endif
  16. /* container_of */
  17. #define container_of(ptr, type, member) \
  18. (type *)((uintptr_t)ptr - offsetof(type,member))
  19. /* The default Nodestore is simply a hash-map from NodeIds to Nodes. To find an
  20. * entry, iterate over candidate positions according to the NodeId hash.
  21. *
  22. * - Tombstone or non-matching NodeId: continue searching
  23. * - Matching NodeId: Return the entry
  24. * - NULL: Abort the search
  25. *
  26. * The nodestore uses atomic operations to set entries of the hash-map. If
  27. * UA_ENABLE_IMMUTABLE_NODES is configured, the nodestore allows read-access
  28. * from an interrupt without seeing corrupted nodes. For true multi-threaded
  29. * access, a mutex is used.
  30. *
  31. * Multi-threading without a mutex could be realized with the Linux RCU mechanism.
  32. * But this is not done for this implementation of the nodestore. */
  33. typedef struct UA_NodeMapEntry {
  34. UA_UInt32 nodeIdHash;
  35. struct UA_NodeMapEntry *orig; /* the version this is a copy from (or NULL) */
  36. UA_UInt16 refCount; /* How many consumers have a reference to the node? */
  37. UA_Boolean deleted; /* Node was marked as deleted and can be deleted when refCount == 0 */
  38. UA_Node node;
  39. } UA_NodeMapEntry;
  40. #define UA_NODEMAP_MINSIZE 64
  41. #define UA_NODEMAP_TOMBSTONE ((UA_NodeMapEntry*)0x01)
  42. typedef struct {
  43. UA_NodeMapEntry **entries;
  44. UA_UInt32 size;
  45. UA_UInt32 count;
  46. UA_UInt32 sizePrimeIndex;
  47. #if UA_MULTITHREADING >= 100
  48. UA_LOCK_TYPE(lock) /* Protect access */
  49. #endif
  50. } UA_NodeMap;
  51. /*********************/
  52. /* HashMap Utilities */
  53. /*********************/
  54. /* The size of the hash-map is always a prime number. They are chosen to be
  55. * close to the next power of 2. So the size ca. doubles with each prime. */
  56. static UA_UInt32 const primes[] = {
  57. 7, 13, 31, 61, 127, 251,
  58. 509, 1021, 2039, 4093, 8191, 16381,
  59. 32749, 65521, 131071, 262139, 524287, 1048573,
  60. 2097143, 4194301, 8388593, 16777213, 33554393, 67108859,
  61. 134217689, 268435399, 536870909, 1073741789, 2147483647, 4294967291
  62. };
  63. static UA_UInt32 mod(UA_UInt32 h, UA_UInt32 size) { return h % size; }
  64. static UA_UInt32 mod2(UA_UInt32 h, UA_UInt32 size) { return 1 + (h % (size - 2)); }
  65. static UA_UInt16
  66. higher_prime_index(UA_UInt32 n) {
  67. UA_UInt16 low = 0;
  68. UA_UInt16 high = (UA_UInt16)(sizeof(primes) / sizeof(UA_UInt32));
  69. while(low != high) {
  70. UA_UInt16 mid = (UA_UInt16)(low + ((high - low) / 2));
  71. if(n > primes[mid])
  72. low = (UA_UInt16)(mid + 1);
  73. else
  74. high = mid;
  75. }
  76. return low;
  77. }
  78. /* Returns an empty slot or null if the nodeid exists or if no empty slot is found. */
  79. static UA_NodeMapEntry **
  80. findFreeSlot(const UA_NodeMap *ns, const UA_NodeId *nodeid) {
  81. UA_UInt32 h = UA_NodeId_hash(nodeid);
  82. UA_UInt32 size = ns->size;
  83. UA_UInt64 idx = mod(h, size); /* Use 64bit container to avoid overflow */
  84. UA_UInt32 startIdx = (UA_UInt32)idx;
  85. UA_UInt32 hash2 = mod2(h, size);
  86. UA_NodeMapEntry **candidate = NULL;
  87. do {
  88. UA_NodeMapEntry *entry = ns->entries[(UA_UInt32)idx];
  89. if(entry > UA_NODEMAP_TOMBSTONE) {
  90. /* A Node with the NodeId does already exist */
  91. if(entry->nodeIdHash == h &&
  92. UA_NodeId_equal(&entry->node.nodeId, nodeid))
  93. return NULL;
  94. } else {
  95. /* Found a candidate node */
  96. if(!candidate)
  97. candidate = &ns->entries[(UA_UInt32)idx];
  98. /* No matching node can come afterwards */
  99. if(entry == NULL)
  100. return candidate;
  101. }
  102. idx += hash2;
  103. if(idx >= size)
  104. idx -= size;
  105. } while((UA_UInt32)idx != startIdx);
  106. return candidate;
  107. }
  108. /* The occupancy of the table after the call will be about 50% */
  109. static UA_StatusCode
  110. expand(UA_NodeMap *ns) {
  111. UA_UInt32 osize = ns->size;
  112. UA_UInt32 count = ns->count;
  113. /* Resize only when table after removal of unused elements is either too
  114. full or too empty */
  115. if(count * 2 < osize && (count * 8 > osize || osize <= UA_NODEMAP_MINSIZE))
  116. return UA_STATUSCODE_GOOD;
  117. UA_NodeMapEntry **oentries = ns->entries;
  118. UA_UInt32 nindex = higher_prime_index(count * 2);
  119. UA_UInt32 nsize = primes[nindex];
  120. UA_NodeMapEntry **nentries = (UA_NodeMapEntry **)UA_calloc(nsize, sizeof(UA_NodeMapEntry*));
  121. if(!nentries)
  122. return UA_STATUSCODE_BADOUTOFMEMORY;
  123. ns->entries = nentries;
  124. ns->size = nsize;
  125. ns->sizePrimeIndex = nindex;
  126. /* recompute the position of every entry and insert the pointer */
  127. for(size_t i = 0, j = 0; i < osize && j < count; ++i) {
  128. if(oentries[i] <= UA_NODEMAP_TOMBSTONE)
  129. continue;
  130. UA_NodeMapEntry **e = findFreeSlot(ns, &oentries[i]->node.nodeId);
  131. UA_assert(e);
  132. *e = oentries[i];
  133. ++j;
  134. }
  135. UA_free(oentries);
  136. return UA_STATUSCODE_GOOD;
  137. }
  138. static UA_NodeMapEntry *
  139. createEntry(UA_NodeClass nodeClass) {
  140. size_t size = sizeof(UA_NodeMapEntry) - sizeof(UA_Node);
  141. switch(nodeClass) {
  142. case UA_NODECLASS_OBJECT:
  143. size += sizeof(UA_ObjectNode);
  144. break;
  145. case UA_NODECLASS_VARIABLE:
  146. size += sizeof(UA_VariableNode);
  147. break;
  148. case UA_NODECLASS_METHOD:
  149. size += sizeof(UA_MethodNode);
  150. break;
  151. case UA_NODECLASS_OBJECTTYPE:
  152. size += sizeof(UA_ObjectTypeNode);
  153. break;
  154. case UA_NODECLASS_VARIABLETYPE:
  155. size += sizeof(UA_VariableTypeNode);
  156. break;
  157. case UA_NODECLASS_REFERENCETYPE:
  158. size += sizeof(UA_ReferenceTypeNode);
  159. break;
  160. case UA_NODECLASS_DATATYPE:
  161. size += sizeof(UA_DataTypeNode);
  162. break;
  163. case UA_NODECLASS_VIEW:
  164. size += sizeof(UA_ViewNode);
  165. break;
  166. default:
  167. return NULL;
  168. }
  169. UA_NodeMapEntry *entry = (UA_NodeMapEntry*)UA_calloc(1, size);
  170. if(!entry)
  171. return NULL;
  172. entry->node.nodeClass = nodeClass;
  173. return entry;
  174. }
  175. static void
  176. deleteEntry(UA_NodeMapEntry *entry) {
  177. UA_Node_clear(&entry->node);
  178. UA_free(entry);
  179. }
  180. static void
  181. cleanupEntry(UA_NodeMapEntry *entry) {
  182. if(entry->deleted && entry->refCount == 0)
  183. deleteEntry(entry);
  184. }
  185. static UA_StatusCode
  186. clearSlot(UA_NodeMap *ns, UA_NodeMapEntry **slot) {
  187. UA_NodeMapEntry *entry = *slot;
  188. if(UA_atomic_cmpxchg((void**)slot, entry, UA_NODEMAP_TOMBSTONE) != entry)
  189. return UA_STATUSCODE_BADINTERNALERROR;
  190. entry->deleted = true;
  191. cleanupEntry(entry);
  192. --ns->count;
  193. /* Downsize the hashmap if it is very empty */
  194. if(ns->count * 8 < ns->size && ns->size > 32)
  195. expand(ns); /* Can fail. Just continue with the bigger hashmap. */
  196. return UA_STATUSCODE_GOOD;
  197. }
  198. static UA_NodeMapEntry **
  199. findOccupiedSlot(const UA_NodeMap *ns, const UA_NodeId *nodeid) {
  200. UA_UInt32 h = UA_NodeId_hash(nodeid);
  201. UA_UInt32 size = ns->size;
  202. UA_UInt64 idx = mod(h, size); /* Use 64bit container to avoid overflow */
  203. UA_UInt32 hash2 = mod2(h, size);
  204. UA_UInt32 startIdx = (UA_UInt32)idx;
  205. do {
  206. UA_NodeMapEntry *entry = ns->entries[(UA_UInt32)idx];
  207. /* Found a candidate */
  208. if(entry > UA_NODEMAP_TOMBSTONE) {
  209. if(entry->nodeIdHash == h &&
  210. UA_NodeId_equal(&entry->node.nodeId, nodeid))
  211. return &ns->entries[(UA_UInt32)idx];
  212. } else {
  213. /* No entry can be found afterwards */
  214. if(entry == NULL)
  215. return NULL;
  216. }
  217. idx += hash2;
  218. if(idx >= size)
  219. idx -= size;
  220. } while((UA_UInt32)idx != startIdx);
  221. return NULL;
  222. }
  223. /***********************/
  224. /* Interface functions */
  225. /***********************/
  226. static UA_Node *
  227. UA_NodeMap_newNode(void *context, UA_NodeClass nodeClass) {
  228. UA_NodeMapEntry *entry = createEntry(nodeClass);
  229. if(!entry)
  230. return NULL;
  231. return &entry->node;
  232. }
  233. static void
  234. UA_NodeMap_deleteNode(void *context, UA_Node *node) {
  235. #if UA_MULTITHREADING >= 100
  236. UA_NodeMap *ns = (UA_NodeMap*)context;
  237. #endif
  238. BEGIN_CRITSECT(ns);
  239. UA_NodeMapEntry *entry = container_of(node, UA_NodeMapEntry, node);
  240. UA_assert(&entry->node == node);
  241. deleteEntry(entry);
  242. END_CRITSECT(ns);
  243. }
  244. static const UA_Node *
  245. UA_NodeMap_getNode(void *context, const UA_NodeId *nodeid) {
  246. UA_NodeMap *ns = (UA_NodeMap*)context;
  247. BEGIN_CRITSECT(ns);
  248. UA_NodeMapEntry **entry = findOccupiedSlot(ns, nodeid);
  249. if(!entry) {
  250. END_CRITSECT(ns);
  251. return NULL;
  252. }
  253. ++(*entry)->refCount;
  254. END_CRITSECT(ns);
  255. return (const UA_Node*)&(*entry)->node;
  256. }
  257. static void
  258. UA_NodeMap_releaseNode(void *context, const UA_Node *node) {
  259. if (!node)
  260. return;
  261. #if UA_MULTITHREADING >= 100
  262. UA_NodeMap *ns = (UA_NodeMap*)context;
  263. #endif
  264. BEGIN_CRITSECT(ns);
  265. UA_NodeMapEntry *entry = container_of(node, UA_NodeMapEntry, node);
  266. UA_assert(&entry->node == node);
  267. UA_assert(entry->refCount > 0);
  268. --entry->refCount;
  269. cleanupEntry(entry);
  270. END_CRITSECT(ns);
  271. }
  272. static UA_StatusCode
  273. UA_NodeMap_getNodeCopy(void *context, const UA_NodeId *nodeid,
  274. UA_Node **outNode) {
  275. UA_NodeMap *ns = (UA_NodeMap*)context;
  276. BEGIN_CRITSECT(ns);
  277. UA_NodeMapEntry **slot = findOccupiedSlot(ns, nodeid);
  278. if(!slot) {
  279. END_CRITSECT(ns);
  280. return UA_STATUSCODE_BADNODEIDUNKNOWN;
  281. }
  282. UA_NodeMapEntry *entry = *slot;
  283. UA_NodeMapEntry *newItem = createEntry(entry->node.nodeClass);
  284. if(!newItem) {
  285. END_CRITSECT(ns);
  286. return UA_STATUSCODE_BADOUTOFMEMORY;
  287. }
  288. UA_StatusCode retval = UA_Node_copy(&entry->node, &newItem->node);
  289. if(retval == UA_STATUSCODE_GOOD) {
  290. newItem->orig = entry; /* Store the pointer to the original */
  291. *outNode = &newItem->node;
  292. } else {
  293. deleteEntry(newItem);
  294. }
  295. END_CRITSECT(ns);
  296. return retval;
  297. }
  298. static UA_StatusCode
  299. UA_NodeMap_removeNode(void *context, const UA_NodeId *nodeid) {
  300. UA_NodeMap *ns = (UA_NodeMap*)context;
  301. BEGIN_CRITSECT(ns);
  302. UA_NodeMapEntry **slot = findOccupiedSlot(ns, nodeid);
  303. UA_StatusCode retval = UA_STATUSCODE_GOOD;
  304. if(slot)
  305. retval = clearSlot(ns, slot);
  306. else
  307. retval = UA_STATUSCODE_BADNODEIDUNKNOWN;
  308. END_CRITSECT(ns);
  309. return retval;
  310. }
  311. static UA_StatusCode
  312. UA_NodeMap_insertNode(void *context, UA_Node *node,
  313. UA_NodeId *addedNodeId) {
  314. UA_NodeMap *ns = (UA_NodeMap*)context;
  315. BEGIN_CRITSECT(ns);
  316. if(ns->size * 3 <= ns->count * 4) {
  317. if(expand(ns) != UA_STATUSCODE_GOOD) {
  318. END_CRITSECT(ns);
  319. return UA_STATUSCODE_BADINTERNALERROR;
  320. }
  321. }
  322. UA_NodeMapEntry **slot;
  323. if(node->nodeId.identifierType == UA_NODEIDTYPE_NUMERIC &&
  324. node->nodeId.identifier.numeric == 0) {
  325. /* Create a random nodeid: Start at least with 50,000 to make sure we
  326. * don not conflict with nodes from the spec. If we find a conflict, we
  327. * just try another identifier until we have tried all possible
  328. * identifiers. Since the size is prime and we don't change the increase
  329. * val, we will reach the starting id again. E.g. adding a nodeset will
  330. * create children while there are still other nodes which need to be
  331. * created. Thus the node ids may collide. */
  332. UA_UInt32 size = ns->size;
  333. UA_UInt64 identifier = mod(50000 + size+1, UA_UINT32_MAX); /* Use 64bit to
  334. * avoid overflow */
  335. UA_UInt32 increase = mod2(ns->count+1, size);
  336. UA_UInt32 startId = (UA_UInt32)identifier; /* mod ensures us that the id
  337. * is a valid 32 bit integer */
  338. do {
  339. node->nodeId.identifier.numeric = (UA_UInt32)identifier;
  340. slot = findFreeSlot(ns, &node->nodeId);
  341. if(slot)
  342. break;
  343. identifier += increase;
  344. if(identifier >= size)
  345. identifier -= size;
  346. } while((UA_UInt32)identifier != startId);
  347. } else {
  348. slot = findFreeSlot(ns, &node->nodeId);
  349. }
  350. if(!slot) {
  351. deleteEntry(container_of(node, UA_NodeMapEntry, node));
  352. END_CRITSECT(ns);
  353. return UA_STATUSCODE_BADNODEIDEXISTS;
  354. }
  355. /* Copy the NodeId */
  356. UA_StatusCode retval = UA_STATUSCODE_GOOD;
  357. if(addedNodeId) {
  358. retval = UA_NodeId_copy(&node->nodeId, addedNodeId);
  359. if(retval != UA_STATUSCODE_GOOD) {
  360. deleteEntry(container_of(node, UA_NodeMapEntry, node));
  361. END_CRITSECT(ns);
  362. return retval;
  363. }
  364. }
  365. /* Store the hash */
  366. UA_NodeMapEntry *newEntry = container_of(node, UA_NodeMapEntry, node);
  367. newEntry->nodeIdHash = UA_NodeId_hash(&node->nodeId);
  368. /* Insert the node */
  369. UA_NodeMapEntry *oldEntry = *slot;
  370. if(UA_atomic_cmpxchg((void**)slot, oldEntry, newEntry) != oldEntry) {
  371. deleteEntry(container_of(node, UA_NodeMapEntry, node));
  372. END_CRITSECT(ns);
  373. return UA_STATUSCODE_BADNODEIDEXISTS;
  374. }
  375. ++ns->count;
  376. END_CRITSECT(ns);
  377. return retval;
  378. }
  379. static UA_StatusCode
  380. UA_NodeMap_replaceNode(void *context, UA_Node *node) {
  381. UA_NodeMap *ns = (UA_NodeMap*)context;
  382. UA_NodeMapEntry *newEntry = container_of(node, UA_NodeMapEntry, node);
  383. BEGIN_CRITSECT(ns);
  384. /* Find the node */
  385. UA_NodeMapEntry **slot = findOccupiedSlot(ns, &node->nodeId);
  386. if(!slot) {
  387. deleteEntry(newEntry);
  388. END_CRITSECT(ns);
  389. return UA_STATUSCODE_BADNODEIDUNKNOWN;
  390. }
  391. UA_NodeMapEntry *oldEntry = *slot;
  392. /* The node was already updated since the copy was made? */
  393. if(oldEntry != newEntry->orig) {
  394. deleteEntry(newEntry);
  395. END_CRITSECT(ns);
  396. return UA_STATUSCODE_BADINTERNALERROR;
  397. }
  398. /* Store the hash */
  399. newEntry->nodeIdHash = oldEntry->nodeIdHash;
  400. /* Replace the entry with an atomic operation */
  401. if(UA_atomic_cmpxchg((void**)slot, oldEntry, newEntry) != oldEntry) {
  402. deleteEntry(newEntry);
  403. END_CRITSECT(ns);
  404. return UA_STATUSCODE_BADINTERNALERROR;
  405. }
  406. oldEntry->deleted = true;
  407. cleanupEntry(oldEntry);
  408. END_CRITSECT(ns);
  409. return UA_STATUSCODE_GOOD;
  410. }
  411. static void
  412. UA_NodeMap_iterate(void *context, UA_NodestoreVisitor visitor,
  413. void *visitorContext) {
  414. UA_NodeMap *ns = (UA_NodeMap*)context;
  415. BEGIN_CRITSECT(ns);
  416. for(UA_UInt32 i = 0; i < ns->size; ++i) {
  417. if(ns->entries[i] > UA_NODEMAP_TOMBSTONE) {
  418. END_CRITSECT(ns);
  419. UA_NodeMapEntry *entry = ns->entries[i];
  420. entry->refCount++;
  421. visitor(visitorContext, &entry->node);
  422. entry->refCount--;
  423. cleanupEntry(entry);
  424. BEGIN_CRITSECT(ns);
  425. }
  426. }
  427. END_CRITSECT(ns);
  428. }
  429. static void
  430. UA_NodeMap_delete(void *context) {
  431. UA_NodeMap *ns = (UA_NodeMap*)context;
  432. #if UA_MULTITHREADING >= 100
  433. UA_LOCK_DESTROY(ns->lock);
  434. #endif
  435. UA_UInt32 size = ns->size;
  436. UA_NodeMapEntry **entries = ns->entries;
  437. for(UA_UInt32 i = 0; i < size; ++i) {
  438. if(entries[i] > UA_NODEMAP_TOMBSTONE) {
  439. /* On debugging builds, check that all nodes were release */
  440. UA_assert(entries[i]->refCount == 0);
  441. /* Delete the node */
  442. deleteEntry(entries[i]);
  443. }
  444. }
  445. UA_free(ns->entries);
  446. UA_free(ns);
  447. }
  448. UA_StatusCode
  449. UA_Nodestore_HashMap(UA_Nodestore *ns) {
  450. /* Allocate and initialize the nodemap */
  451. UA_NodeMap *nodemap = (UA_NodeMap*)UA_malloc(sizeof(UA_NodeMap));
  452. if(!nodemap)
  453. return UA_STATUSCODE_BADOUTOFMEMORY;
  454. nodemap->sizePrimeIndex = higher_prime_index(UA_NODEMAP_MINSIZE);
  455. nodemap->size = primes[nodemap->sizePrimeIndex];
  456. nodemap->count = 0;
  457. nodemap->entries = (UA_NodeMapEntry**)
  458. UA_calloc(nodemap->size, sizeof(UA_NodeMapEntry*));
  459. if(!nodemap->entries) {
  460. UA_free(nodemap);
  461. return UA_STATUSCODE_BADOUTOFMEMORY;
  462. }
  463. #if UA_MULTITHREADING >= 100
  464. UA_LOCK_INIT(nodemap->lock)
  465. #endif
  466. /* Populate the nodestore */
  467. ns->context = nodemap;
  468. ns->clear = UA_NodeMap_delete;
  469. ns->newNode = UA_NodeMap_newNode;
  470. ns->deleteNode = UA_NodeMap_deleteNode;
  471. ns->getNode = UA_NodeMap_getNode;
  472. ns->releaseNode = UA_NodeMap_releaseNode;
  473. ns->getNodeCopy = UA_NodeMap_getNodeCopy;
  474. ns->insertNode = UA_NodeMap_insertNode;
  475. ns->replaceNode = UA_NodeMap_replaceNode;
  476. ns->removeNode = UA_NodeMap_removeNode;
  477. ns->iterate = UA_NodeMap_iterate;
  478. return UA_STATUSCODE_GOOD;
  479. }