cap.c 24.8 KB
Newer Older
Anton Burtsev's avatar
Anton Burtsev committed
1
#include <lcd/cap.h>
2

3
4
5
// this function will not lock any semaphore.
// assumption is that cdt and cspace are already locked.
bool lcd_cap_delete_internal_lockless(struct cte *cap, bool *last_reference)
6
{
7
8
9
	struct cte *table;
	struct cap_derivation_tree *p_cdt, *cdt, *c_cdt, *prev_cdt = NULL;
	*last_reference = false;
10
  
11
 
12
13
14
15
16
	if (cap == NULL)
	{
		LCD_PANIC("lcd_cap_delete_internal: Invalid Input\n");
		return false;
	}
17

18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
	cdt = cap->cap.cdt_node;
	p_cdt = cdt->parent_ptr;
	c_cdt = cdt->child_ptr;
	if (p_cdt == NULL && c_cdt == NULL && cdt->next == NULL && cdt->prev == NULL)
		*last_reference = true;
  
	// update parent pointer
	while (c_cdt != NULL)
	{
		prev_cdt = c_cdt;
		c_cdt->parent_ptr = p_cdt;
		c_cdt = c_cdt->next;
	}
	c_cdt = cdt->child_ptr;
  
	// update sibling pointers
	if (c_cdt == NULL)
	{
		if (cdt->prev != NULL)
		{
			cdt->prev->next = cdt->next;
		}
		if (cdt->next != NULL)
		{
			cdt->next->prev = cdt->prev;
		}
	}
	else
	{
		if (cdt->prev != NULL)
		{
			cdt->prev->next = c_cdt;
			c_cdt->prev = cdt->prev;
			cdt->prev = NULL;
		}
		if (cdt->next != NULL)
		{
			prev_cdt->next = cdt->next;
			cdt->next->prev = c_cdt;
			cdt->next = NULL;
		}
	}
60
    
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
	// update child pointer
	if (p_cdt->child_ptr == cdt)
	{
		if (c_cdt != NULL)
		{
			p_cdt->child_ptr = c_cdt;
		}
		else
		{
			p_cdt->child_ptr = cdt->next;
		}
	}
  
	// delete the capability
	kfree(cdt);
	cap->ctetype = lcd_type_free;
	table = cap - cap->index;
	cap->slot.next_free_cap_slot = table[0].slot.next_free_cap_slot;
	table[0].slot.next_free_cap_slot = cap->index;
	return true;
81
82
}

83
84
bool lcd_cap_delete_internal(struct cte *cap, bool *last_reference)
{
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
	struct cap_space *cspace;
	struct cte *node;
	bool done = false;
	if (cap == NULL || last_reference == NULL)
		return false;
	*last_reference = false;
	node = cap - cap->index;
	if (node[0].ctetype != lcd_type_free)
		return false;
	cspace = node[0].slot.cspace;
	if (cspace == NULL)
		return false;
  
	while (!done)
	{
		// lock the cspace
		if (down_trylock(&(cspace->sem_cspace)) == 0)
		{
			lcd_cap_delete_internal_lockless(cap, last_reference);
			done = true;
		}
		else
		{
			msleep_interruptible(1);
		}
	}
	return true;
112
113
114
115
}

uint32_t lcd_cap_delete_capability(struct task_struct *tcb, cap_id cid)
{
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
	struct cte *cap;
	bool last_reference = false;
	struct semaphore *sem_cdt_backup;
	if (tcb == NULL || cid <= 0)
	{
		LCD_PANIC("lcd_cap_delete_capability: Invalid Input\n");
		return -1;
	}
  
	cap = lcd_cap_lookup_capability(tcb, cid, true);
	if (cap == NULL)
	{
		LCD_PANIC("lcd_cap_delete_capability: Capability not found\n");
		return -1;
	}
	sem_cdt_backup = cap->cap.cdt_node->sem_cdt;
	lcd_cap_delete_internal(cap, &last_reference);
	up(sem_cdt_backup);
	if (last_reference == true)
	{
		// TBD: this is the place where we free the object associated with teh capability.
		// for now we just release the sem_cdt semaphore.
		kfree(sem_cdt_backup);
	}
	return 0;
141
142
143
144
}

uint32_t lcd_cap_revoke_capability(struct task_struct *tcb, cap_id cid)
{
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
	struct cte *cap;
	struct cap_derivation_tree *cdt, *c_cdt;
	struct kfifo cap_q;
	struct semaphore *sem_cdt_backup;
	int size = sizeof(struct cte);
	bool dummy = false, last_reference = false;
  
	if (tcb == NULL || cid <= 0)
	{
		LCD_PANIC("lcd_cap_delete_capability: Invalid Input\n");
		return -1;
	}
  
	if (kfifo_alloc(&cap_q, sizeof(struct cte) * 512, GFP_KERNEL) != 0)
	{
		LCD_PANIC("lcd_cap_revoke_capability: Fifo allocation failed, aborting\n");
		return -1;
	}
  
	cap = lcd_cap_lookup_capability(tcb, cid, true);
	if (cap == NULL)
	{
		LCD_PANIC("lcd_cap_delete_capability: Capability not found\n");
		return -1;
	}
	cdt = cap->cap.cdt_node;
	sem_cdt_backup = cap->cap.cdt_node->sem_cdt;
	if (cdt->parent_ptr == NULL && cdt->next == NULL && cdt->prev == NULL)
		last_reference = true;
174
    
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
	kfifo_in(&cap_q, cap, size);
  
	while (!kfifo_is_empty(&cap_q))
	{
		kfifo_out(&cap_q, cap, size);
		if (cap == NULL || cap->ctetype != lcd_type_capability)
			continue;
		cdt = cap->cap.cdt_node;
		c_cdt = cdt->child_ptr;
		while (c_cdt != NULL)
		{
			kfifo_in(&cap_q, c_cdt->cap, size);
			c_cdt = c_cdt->next;
		}
		lcd_cap_delete_internal(cap, &dummy);
	}
	up(sem_cdt_backup);
	// with revoke the entire tree is deleted. Now if the root of the tree had not parent,
	// or no siblings then this was the true last_reference so we now remove the cdt semaphore.
	if (last_reference)
	{ 
		kfree(sem_cdt_backup);
	}
	return 0;
199
200
201
}


202
void lcd_cap_destroy_cspace(struct task_struct *tcb)
203
{
204
205
206
207
208
209
210
211
212
213
214
215
216
217
	struct cte *cnode, *node, level_separator;
	struct kfifo cnode_q;
	int size = sizeof(struct cte);
	struct cap_space *cspace;
	int depth_count = 0, i;
	struct semaphore *sem_cdt_backup;
	bool cspace_locked = false, table_visited = false, last_reference = false;
  
	if (tcb == NULL)
	{
		ASSERT(false, "lcd_cap_destroy_cspace: Invalid Input\n");
		return;
	}
	cspace = tcb->cspace;
218

219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
	if (kfifo_alloc(&cnode_q, sizeof(struct cte) * 512, GFP_KERNEL) != 0)
	{
		ASSERT(false, "lcd_cap_destroy_cspace: Failed to allcoate kfifo, cspace cannot be destroyed\n");
		return;
	}
	if (cspace->root_cnode.cnode.table != NULL)
		kfifo_in(&cnode_q, &(cspace->root_cnode), size);
	level_separator.ctetype = lcd_type_separator;
	kfifo_in(&cnode_q, &level_separator, size);
  
	while (!kfifo_is_empty(&cnode_q) && depth_count < MAX_DEPTH)
	{
		if (cspace_locked || down_trylock(&(cspace->sem_cspace)) == 0)
		{
			cspace_locked = true;
			cspace->root_cnode.ctetype = lcd_type_invalid;
			if (!table_visited)
			{
				kfifo_out(&cnode_q, cnode, size);
				if (cnode->ctetype == lcd_type_separator)
				{
					depth_count++;
					if (kfifo_is_empty(&cnode_q))
					{
						up(&(cspace->sem_cspace));
						cspace_locked = false;
						break;
					}
					else
					{
						kfifo_in(&cnode_q, &level_separator, size);
						continue;
					}
				}
				node = cnode->cnode.table;
				if (node == NULL)
				{
					// we may have a cycle or the tables are corrupted
					up(&(cspace->sem_cspace));
					cspace_locked = false;
					break;
				}
				// push all its cnode to cnode_q
				for (i = CNODE_SLOTS_START; i < MAX_SLOTS; i++)
				{
					if (node[i].ctetype == lcd_type_cnode)
					{
						if (node[i].cnode.table != NULL)
							kfifo_in(&cnode_q, &(node[i]), size);
					}
				}
				table_visited = true;
				i = 1;
			} // if (!table_visited)
			for (; i < CNODE_SLOTS_START; i++)
			{
				if (node[i].ctetype == lcd_type_free)
					continue;
				// try to get the CDT lock ... recipe for deadlock- Revoke, Delete and delete_internal
				// access the locks in the order CDT Lock and then CSPACE lock, but this function
				// tries to access them in order CSPACE and then CDT. Be very careful while modifying
				// this function or the lock access patterns in this and the related functions.
				if (down_trylock(node[i].cap.cdt_node->sem_cdt) == 0)
				{
					sem_cdt_backup = node[i].cap.cdt_node->sem_cdt;
					last_reference = false;
					lcd_cap_delete_internal_lockless(&(node[i]), &last_reference);
					up(sem_cdt_backup);
					if (last_reference == true)
					{
						// TBD: this is the place where we can free the object associated with the cap.
						// for now just free sem_cdt.
						kfree(node[i].cap.cdt_node->sem_cdt);
					}
				}
				else
				{
					up(&(cspace->sem_cspace));
					cspace_locked = false;
					break;
				}
			}
			if (i == CNODE_SLOTS_START)
			{
				kfree(node);
				table_visited = false;
			}
			else
			{
				msleep_interruptible(1);
			}
			if (kfifo_is_empty(&cnode_q) || depth_count >= MAX_DEPTH)
			{
				up(&(cspace->sem_cspace));
				cspace_locked = false;
			}
		} // if down_trylock(cspace->sem_cspace)
	} // while (!kfifo_is_empty(&cnode_q) && depth_count < MAX_DEPTH)
	kfifo_free(&cnode_q);
	kfree(cspace);
	tcb->cspace = NULL;
	return;
321
322
}

323
cap_id lcd_cap_grant_capability(struct task_struct *stcb, cap_id src_cid, struct task_struct *dtcb, lcd_cap_rights crights)
324
{
325
326
327
328
329
330
331
332
333
334
	cap_id cid = 0;
	struct cap_space *src_cspace, *dst_cspace;
	struct cte *src_cte = NULL, *dst_cte = NULL;
	bool done = false;
	struct cap_derivation_tree *dst_cdt_node = kmalloc(sizeof(struct cap_derivation_tree), GFP_KERNEL);
	if (dst_cdt_node == NULL)
	{
		ASSERT(false, "lcd_cap_grant: Failed to allocate cdt node");
		return 0;
	}
335

336
337
338
339
340
341
342
343
344
345
346
347
	if (stcb == NULL || dtcb == NULL || src_cid <= 0)
	{
		ASSERT(false, "lcd_cap_grant: Invalid Inputs\n");
		kfree(dst_cdt_node);
		return 0;
	}
	src_cspace = stcb->cspace;
	dst_cspace = dtcb->cspace;
	while (!done)
	{
		struct cap_derivation_tree *src_cdt_node;
		struct cap_derivation_tree *cdtnode;
348
    
349
350
351
352
353
354
355
356
357
358
		// Lookup the source TCB to get a pointer to capability and keep the cdt locked.
		src_cte = lcd_cap_lookup_capability(stcb, src_cid, true);
		if (src_cte == NULL || src_cte->ctetype != lcd_type_capability)
		{
			LCD_PANIC("lcd_cap_grant_capability: Invalid Capability\n");
			if (src_cte != NULL)
				up(src_cte->cap.cdt_node->sem_cdt);
			kfree(dst_cdt_node);
			return 0;
		}
359
    
360
361
362
363
364
365
366
		if  ((src_cte->cap.crights & CAPRIGHTS_GRANT) == 0)
		{
			LCD_PANIC("lcd_cap_grant_capability: Source does not have grant permissions\n");
			up(src_cte->cap.cdt_node->sem_cdt);
			kfree(dst_cdt_node);
			return 0;
		}
367
    
368
369
370
371
372
373
374
375
376
377
378
379
380
		src_cdt_node = src_cte->cap.cdt_node;
		cdtnode = src_cdt_node->child_ptr;
		// lock the destination cspace
		if (down_trylock(&(dst_cspace->sem_cspace)) == 0)
		{
			if (dst_cspace->root_cnode.ctetype == lcd_type_invalid)
			{
				LCD_PANIC("lcd_cap_grant_capability: Destroy may be in progress, aborting operation\n");
				up(&(dst_cspace->sem_cspace));
				up(src_cte->cap.cdt_node->sem_cdt);
				kfree(dst_cdt_node);
				return 0;
			}
381
      
382
383
384
385
386
387
388
389
390
391
392
393
394
			// get a free slot in destination.
			if (cid == 0)
			{
				cid = lcd_cap_lookup_freeslot(dst_cspace, &dst_cte);
			}
			if (dst_cte == NULL || dst_cte->ctetype != lcd_type_free)
			{
				LCD_PANIC("lcd_cap_grant_capability: No free slot\n");
				up(&(dst_cspace->sem_cspace));
				up(src_cte->cap.cdt_node->sem_cdt);
				kfree(dst_cdt_node);
				return 0;
			}
395
      
396
397
398
399
400
			// add the capability to destination.
			dst_cte->cap.crights = (crights & src_cte->cap.crights);
			dst_cte->cap.hobject = src_cte->cap.hobject;
			dst_cdt_node->sem_cdt = src_cte->cap.cdt_node->sem_cdt;
			dst_cte->cap.cdt_node = dst_cdt_node;
401
    
402
403
404
405
406
			src_cdt_node->child_ptr = dst_cdt_node;
			dst_cdt_node->parent_ptr = src_cdt_node;
			dst_cdt_node->child_ptr  = NULL;
			dst_cdt_node->next = cdtnode;
			dst_cdt_node->prev = NULL;
407
      
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
			if (cdtnode)
			{
				cdtnode->prev = dst_cdt_node;
			}
			dst_cte->ctetype = lcd_type_capability;
			done = true;
			up(&(dst_cspace->sem_cspace));
			up(src_cte->cap.cdt_node->sem_cdt);
			break;
		}
		up(src_cte->cap.cdt_node->sem_cdt);
		if (!done)
			msleep_interruptible(1);
	}
	return cid;
423
424
425
426
}

uint32_t lcd_cap_get_rights(struct task_struct *tcb, cap_id cid, lcd_cap_rights *rights)
{
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
	struct cte       *cap;
  
	if (tcb == NULL || tcb->cspace == NULL || cid == 0 || rights == NULL)
	{
		ASSERT(false, "lcd_get_cap_rights: Invalid Inputs\n");
		return -1;
	}
	cap = lcd_cap_lookup_capability(tcb, cid, false);
	if (cap == NULL || cap->ctetype != lcd_type_capability)
	{
		ASSERT(false, "lcd_get_cap_rights: Invalid capability identifier\n");
		return -1;
	}
	*rights = cap->cap.crights;
	return 0;
442
443
444
445
446
}

// does not lock the cspace caller responsbile for the same.
// Given a task_struct and a capability identifier, will return the pointer to the 
// capability table entry associated with that identifier within the cspace of the thread.
447
struct cte * lcd_cap_lookup_capability(struct task_struct *tcb, cap_id cid, bool keep_locked)
448
{
449
450
451
452
453
	struct cte *cap = NULL, *node = NULL;
	struct cap_space *cspace;
	cap_id id = cid;
	int index = 0;
	int mask = (~0);
454
    
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
	// check if input is valid
	if (tcb == NULL || cid == 0)
	{
		ASSERT(false, "lcd_lookup_capability: Invalid Inputs\n");
		return NULL;
	}
	cspace = tcb->cspace;
  
	mask = mask << (CNODE_INDEX_BITS);
	mask = ~mask;
  
	if (cspace == NULL || cspace->root_cnode.cnode.table == NULL)
	{
		ASSERT(false, "lcd_lookup_capability: Invalid/Corrupted cspace\n");
		return NULL;
	}
	node = cspace->root_cnode.cnode.table;
  
	while (id > 0)
	{
		index = (int)(id) & mask;
		id = id >> (CNODE_INDEX_BITS);
		if (node[index].ctetype == lcd_type_capability && id == 0)
		{
			// delete/revoke could be accessing the same node
			// try to lock it and confirm if still valid.
			if (down_interruptible(node[index].cap.cdt_node->sem_cdt) == 0)
			{
				if (node[index].ctetype == lcd_type_capability)
				{
					cap = &node[index];
				}
				else
				{
					up(node[index].cap.cdt_node->sem_cdt);
				}
				if (!keep_locked)
					up(node[index].cap.cdt_node->sem_cdt);
			}
			break;
		}
		else if (node[index].ctetype == lcd_type_cnode && id != 0)
		{
			node = node[index].cnode.table;
		}
		else
		{
			ASSERT(false, "lcd_lookup_capability: Invalid Capability Identifier\n");
			break;
		}
	}
  
	return cap;
508
509
510
511
}

cap_id lcd_cap_create_capability(struct task_struct *tcb, void * hobject, lcd_cap_rights crights)
{
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
	struct cap_space *cspace;
	struct cte       *cap;
	cap_id           cid;
	struct cap_derivation_tree *cdtnode;
  
	if (tcb == NULL)
	{
		LCD_PANIC("lcd_cap_create_capability: Invalid Input\n");
		return 0;
	}
	cspace = tcb->cspace;
  
	if (cspace == NULL || cspace->root_cnode.cnode.table == NULL)
	{
		LCD_PANIC("lcd_cap_create_capability: Invalid TCB\n");
		return 0;
	}
  
	cdtnode = kmalloc(sizeof(struct cap_derivation_tree), GFP_KERNEL);
	if (cdtnode == NULL)
	{
		LCD_PANIC("lcd_cap_create_capability: CDT Node allocation failed\n");
		return 0;
	}
  
	cdtnode->sem_cdt = kmalloc(sizeof(struct semaphore), GFP_KERNEL);
	if (cdtnode == NULL)
	{
		LCD_PANIC("lcd_cap_create_capability: CDT Semaphore allocation failed\n");
		kfree(cdtnode);
		return 0;
	}
  
	if (down_interruptible(&(cspace->sem_cspace)))
	{
		if (cspace->root_cnode.ctetype == lcd_type_invalid)
		{
			LCD_PANIC("lcd_cap_create_capability: Destroy may be in progress, operation aborted\n");
			up(&(cspace->sem_cspace));
			kfree(cdtnode->sem_cdt);
			kfree(cdtnode);
			return 0;
		}
		cid = lcd_cap_lookup_freeslot(cspace, &cap);
		if (cid == 0)
		{
			LCD_PANIC("lcd_cap_create_capability: No Free Slot found\n");
			kfree(cdtnode->sem_cdt);
			kfree(cdtnode);
			up(&(cspace->sem_cspace));
			return 0;
		}
564
    
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
		cap->ctetype = lcd_type_capability;  
		cap->cap.crights = crights;
		cap->cap.hobject = hobject;
		sema_init(cdtnode->sem_cdt, 1);
		cap->cap.cdt_node = cdtnode;
		cap->cap.cdt_node->cap = cap;
		cap->cap.cdt_node->child_ptr  = NULL;
		cap->cap.cdt_node->parent_ptr = NULL;
		cap->cap.cdt_node->prev = NULL;
		cap->cap.cdt_node->next = NULL;
		up(&(cspace->sem_cspace));
	}
	else
	{
		LCD_PANIC("lcd_cap_create_capability: Signal interrupted cspace lock acquire\n");
		kfree(cdtnode->sem_cdt);
		kfree(cdtnode);
	}
	return cid;
584
585
586
587
}

struct cap_space * lcd_cap_create_cspace(void *objects[], lcd_cap_rights rights[])
{
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
	int i;
	bool success = false;
	struct cte *table;
	struct cap_derivation_tree *cdtnode;
	struct task_struct *tcb = objects[LCD_CapInitThreadTCB];
	struct cap_space *cspace = kmalloc(sizeof(struct cap_space), GFP_KERNEL);
  
	if (cspace == NULL)
	{
		LCD_PANIC("lcd_cap_create_cspace: Failed to allocate memory for cspace\n");
		return NULL;
	}
	cspace->root_cnode.cnode.table = NULL;
	if (tcb == NULL)
	{
		LCD_PANIC("lcd_create_cspace: LCD_CapInitThreadTCB cannot be NULL\n");
		goto create_cspace_safe_exit;
	}
	if ((sizeof(objects)/sizeof(objects[0]) != LCD_CapFirstFreeSlot) ||
		(sizeof(rights)/sizeof(rights[0]) != LCD_CapFirstFreeSlot))
	{
		LCD_PANIC("lcd_create_cspace: Invalid inputs, size of arrays should be equal to LCD_CapFirstFreeSlot\n");
		goto create_cspace_safe_exit;
	}
  
	// initialize semaphore
	sema_init(&(cspace->sem_cspace), 1);
	if (down_interruptible(&(cspace->sem_cspace)))
	{
		// allocate memory for the first cnode.
		cspace->root_cnode.ctetype = lcd_type_cnode;
		cspace->root_cnode.cnode.cnode_id = 0;
		cspace->root_cnode.cnode.table_level = 0;
		cspace->root_cnode.cnode.table = kmalloc(PAGE_SIZE, GFP_KERNEL);
		if (cspace->root_cnode.cnode.table == NULL)
		{
			LCD_PANIC("lcd_cap_create_cspace: Failed to allocate cnode table\n");
			goto create_cspace_safe_exit;
		}
627

628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
		table = cspace->root_cnode.cnode.table;
		table[0].ctetype = lcd_type_free;
		// Get the intitial capabilities into the cspace.
		for (i = 1; i < LCD_CapFirstFreeSlot; i++)
		{
			table[i].cap.hobject = objects[i];
			table[i].cap.crights = rights[i];
			if (objects[i] == NULL)
			{
				table[i].ctetype = lcd_type_invalid;
				continue;
			}
			table[i].ctetype = lcd_type_capability;
			cdtnode = kmalloc(sizeof(struct cap_derivation_tree), GFP_KERNEL);
			if (cdtnode == NULL)
			{
				LCD_PANIC("lcd_cap_create_cspace: Failed to allocate cdt node\n");
				goto create_cspace_safe_exit;
			}
			cdtnode->cap = &(cspace->root_cnode.cnode.table[i]);
			cdtnode->sem_cdt = kmalloc(sizeof(struct semaphore), GFP_KERNEL);
			if (cdtnode->sem_cdt == NULL)
			{
				LCD_PANIC("lcd_cap_create_cspace: Failed to allocate cdt semaphore\n");
				goto create_cspace_safe_exit;
			}
			sema_init(cdtnode->sem_cdt, 1);
			cdtnode->parent_ptr = NULL;
			cdtnode->child_ptr = NULL;
			cdtnode->next = NULL;
			cdtnode->prev = NULL;
			table[i].cap.cdt_node = cdtnode;
		}
661

662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
		// initialize the free list
		success = lcd_cap_initialize_freelist(cspace, cspace->root_cnode.cnode.table, true);
		up(&(cspace->sem_cspace));
		if (!success)
		{
			LCD_PANIC("lcd_cap_create_cspace: Failed to initialize free list\n");
			goto create_cspace_safe_exit;
		}
	}
	else
	{
		LCD_PANIC("lcd_cap_create_cspace: Failed to acquire cspace lock\n");
		goto create_cspace_safe_exit;
	}
  
	tcb->cspace = cspace;
	return cspace;
679
680
  
create_cspace_safe_exit:
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
	if (cspace)
	{
		if (cspace->root_cnode.cnode.table)
		{
			for (i = 1; i < LCD_CapFirstFreeSlot; i++)
			{
				if (cspace->root_cnode.cnode.table[i].cap.cdt_node != NULL)
				{
					if (cspace->root_cnode.cnode.table[i].cap.cdt_node->sem_cdt != NULL)
					{
						kfree(cspace->root_cnode.cnode.table[i].cap.cdt_node->sem_cdt);
					}
					kfree(cspace->root_cnode.cnode.table[i].cap.cdt_node);
				}
			}
			kfree(cspace->root_cnode.cnode.table);
			cspace->root_cnode.cnode.table = NULL;
		}
		kfree(cspace);
		tcb->cspace = NULL;
	}
	return NULL;
703
704
705
706
707
}

// does not lock the cspace.
// First entry of every cnode table will be the head of the free slots available
// in the table. This function will just populate the free list.
708
bool lcd_cap_initialize_freelist(struct cap_space *cspace, struct cte *cnode, bool bFirstCNode)
709
{
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
	int startid = 1;
	int i;
  
	if (cnode == NULL || cspace == NULL)
		return false;
  
	if (bFirstCNode)
	{
		startid = LCD_CapFirstFreeSlot;
	}
  
	cnode[0].ctetype = lcd_type_invalid;
	cnode[0].slot.cspace = cspace;
	cnode[0].ctetype = lcd_type_free;
	cnode[0].index = 0;
	cnode[0].slot.next_free_cap_slot = startid;
	cnode[startid].ctetype = lcd_type_free;
	for (i = startid; i < CNODE_SLOTS_START - 1; i++)
	{
		cnode[i].slot.next_free_cap_slot = i + 1;
		cnode[i+1].ctetype = lcd_type_free;
		cnode[i].index = i;
	}
	cnode[i].slot.next_free_cap_slot = 0;
	cnode[i].index = i;
  
	startid = CNODE_SLOTS_START;
	cnode[0].slot.next_free_cnode_slot = startid;
	cnode[startid].ctetype = lcd_type_free;
	for (i = CNODE_SLOTS_START; i < MAX_SLOTS - 1; i++)
	{
		cnode[i].slot.next_free_cnode_slot = i + 1;
		cnode[i].index = i;
		cnode[i+1].ctetype = lcd_type_free;
	}
	cnode[i].slot.next_free_cnode_slot = 0;
	cnode[i].index = i;
	return true;
748
749
750
751
752
}

// Removes the free_slot from free list.
struct cte * lcd_cap_reserve_slot(struct cte *cnode, cap_id *cid, int free_slot)
{
753
754
755
756
757
758
	struct cte *node = cnode->cnode.table;
	ASSERT(node[free_slot].ctetype == lcd_type_free, "Free List is corrupted\n");
	// a valid empty slot
	node[0].slot.next_free_cap_slot = node[free_slot].slot.next_free_cap_slot;
	lcd_set_bits_at_level(cnode, cid, free_slot);
	return &node[free_slot];
759
760
761
762
763
764
765
766
767
768
}


// free slot will be booked for the caller.
// ie. it will not longer be free once this function returns it.
// naming convention:
// cnode = struct cte entry in the table, which points to another table.
// node = pointer the the array of struct cte entries/capability table i.e. cnode->cnode.table
cap_id lcd_cap_lookup_freeslot(struct cap_space *cspace, struct cte **cap)
{
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
	cap_id cid = 0, cnode_id;
	bool found = false;
	int i = 0;
	int size = sizeof(struct cte);
	struct kfifo cnode_q;
  
	if (cspace == NULL || cspace->root_cnode.cnode.table == NULL || cap == NULL)
	{
		LCD_PANIC("lcd_cap_lookup_freeslot: Invalid Inputs\n");
		return 0;
	}
  
	if (kfifo_alloc(&cnode_q, sizeof(struct cte) * 512, GFP_KERNEL) != 0)
	{
		LCD_PANIC("lcd_cap_lookup_freeslot: Failed to allocate FIFO buffer\n");
		return 0;
	}
786

787
	kfifo_in(&cnode_q, &(cspace->root_cnode), size);
788
  
789
790
791
792
	while (!found && !kfifo_is_empty(&cnode_q))
	{
		int free_cap_slot = 0, free_cnode_slot = 0;
		struct cte *node = NULL, *cnode = NULL;
793
    
794
795
796
797
798
		kfifo_out(&cnode_q, cnode, size);
		if (cnode == NULL)
		{
			break;
		}
799
    
800
		node = cnode->cnode.table;
801
    
802
803
		free_cap_slot   = node[0].slot.next_free_cap_slot;
		free_cnode_slot = node[0].slot.next_free_cnode_slot;
804
    
805
806
807
808
809
		if (free_cap_slot != 0 && free_cap_slot < CNODE_SLOTS_START)
		{
			*cap = lcd_cap_reserve_slot(cnode, &cid, free_cap_slot);
			break;
		}
810
    
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
		if (free_cnode_slot != 0 && free_cnode_slot >= CNODE_SLOTS_START && free_cnode_slot < MAX_SLOTS)
		{
			// there is no slot free for capability
			// 1. Check if free slots are available at next level
			for (i = CNODE_SLOTS_START; i < free_cnode_slot; i++)
			{
				struct cte * next_cnode = &node[i];
				struct cte *next_node = node[i].cnode.table; 
				free_cap_slot = next_node[0].slot.next_free_cap_slot;
				if (free_cap_slot != 0 && free_cap_slot < CNODE_SLOTS_START)
				{
					*cap = lcd_cap_reserve_slot(next_cnode, &cid, free_cap_slot);
					found = true;
					break;
				}
			}
			if (found)
				break;
829
      
830
831
832
833
834
835
836
837
838
839
840
841
842
			// we will have to allocate a new cnode
			node[free_cnode_slot].cnode.table = kmalloc(PAGE_SIZE, GFP_KERNEL);
			if (node[free_cnode_slot].cnode.table == NULL)
			{
				LCD_PANIC("lcd_cap_lookup_freeslot: Not able to allocate cnode\n");
				break;
			}
			node[0].slot.next_free_cnode_slot = node[free_cnode_slot].slot.next_free_cnode_slot;
			node[free_cnode_slot].ctetype = lcd_type_cnode;
			lcd_cap_initialize_freelist(cspace, node[free_cnode_slot].cnode.table, false);
			node[free_cnode_slot].cnode.table_level = cnode->cnode.table_level + 1;
			lcd_set_bits_at_level(cnode, &cnode_id, free_cnode_slot);
			node[free_cnode_slot].cnode.cnode_id = cnode_id;
843
      
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
			cnode = &node[free_cnode_slot];
			node = node[free_cnode_slot].cnode.table;
			free_cap_slot = node[0].slot.next_free_cap_slot;
			if (free_cap_slot != 0 && free_cap_slot < CNODE_SLOTS_START)
			{
				*cap = lcd_cap_reserve_slot(cnode, &cid, free_cap_slot);
			}
			break;
		} // found a free cnode slot
		else 
		{
			// nothing is free in this cnode 
			// kep lookin at all its children
			for (i = CNODE_SLOTS_START; i < MAX_SLOTS; i++)
			{
				kfifo_in(&cnode_q, &node[i], size);
			}
		}
	} // while (!kfifo_is_empty())
	kfifo_free(&cnode_q);
	return cid;
865
866
}

867
868
cap_id lcd_cap_mint_capability(struct task_struct *tcb, cap_id cid, lcd_cap_rights rights)
{
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
	cap_id id = 0;
	struct cap_space *cspace;
	struct cte *src_cte = NULL, *dst_cte = NULL;
	struct cap_derivation_tree *cdt;
	struct cap_derivation_tree *dst_cdt;
	bool done = false;
  
	if (tcb == NULL || cid == 0)
	{
		LCD_PANIC("lcd_cap_mint_capability: Invalid Inputs\n");
		return 0;
	}
	cspace = tcb->cspace;
  
  
	dst_cdt = kmalloc(sizeof(struct cap_derivation_tree), GFP_KERNEL);
	if (dst_cdt == NULL)
	{
		LCD_PANIC("lcd_cap_mint_capability: Failed to allocate memory for cdt node\n");
		return 0;
	}
	while (!done)
	{
		// keep the source cdt locked.
		src_cte = lcd_cap_lookup_capability(tcb, cid, true);
		if (src_cte == NULL || src_cte->ctetype != lcd_type_capability)
		{
			LCD_PANIC("lcd_cap_mint_capability: Invalid Capability\n");
			if (src_cte != NULL)
				up(src_cte->cap.cdt_node->sem_cdt);
			kfree(dst_cdt);
			return 0;
		}
		cdt = src_cte->cap.cdt_node;
		if (down_trylock(&(cspace->sem_cspace)) == 0)
		{
			if (cspace->root_cnode.ctetype == lcd_type_invalid)
			{
				LCD_PANIC("lcd_cap_mint_capability: Destroy may be in progress, aborting operation\n");
				up(&(cspace->sem_cspace));
				up(cdt->sem_cdt);
				kfree(dst_cdt);
				return 0;
			}
913
      
914
915
916
917
918
919
920
921
922
923
924
925
926
			// get a free slot in destination.
			if (id == 0)
			{
				id = lcd_cap_lookup_freeslot(cspace, &dst_cte);
			}
			if (dst_cte == NULL || dst_cte->ctetype != lcd_type_free)
			{
				LCD_PANIC("lcd_cap_mint_capability: No free slot\n");
				up(&(cspace->sem_cspace));
				up(cdt->sem_cdt);
				kfree(dst_cdt);
				return 0;
			}
927
      
928
929
930
931
932
			// add the capability in cspace and cdt node as a sibling.
			dst_cte->cap.crights = (rights & src_cte->cap.crights);
			dst_cte->cap.hobject = src_cte->cap.hobject;
			dst_cdt->sem_cdt = cdt->sem_cdt;
			dst_cte->cap.cdt_node = dst_cdt;
933
    
934
935
936
937
938
939
940
			dst_cdt->next = cdt->next;
			if (cdt->next != NULL)
				cdt->next->prev = dst_cdt;
			cdt->next = dst_cdt;
			dst_cdt->prev = cdt;
			dst_cdt->child_ptr  = NULL;
			dst_cdt->parent_ptr = cdt->parent_ptr;
941
      
942
943
944
945
946
947
948
949
950
951
			dst_cte->ctetype = lcd_type_capability;
			done = true;
			up(&(cspace->sem_cspace));
		}
		up(cdt->sem_cdt);
		if (!done)
			msleep_interruptible(1);
	}  
  
	return id;
952
}