1#include <linux/dma-mapping.h>
2#include <asm/iommu_table.h>
3#include <linux/string.h>
4#include <linux/kallsyms.h>
5
6
7#define DEBUG 1
8
9static struct iommu_table_entry * __init
10find_dependents_of(struct iommu_table_entry *start,
11		   struct iommu_table_entry *finish,
12		   struct iommu_table_entry *q)
13{
14	struct iommu_table_entry *p;
15
16	if (!q)
17		return NULL;
18
19	for (p = start; p < finish; p++)
20		if (p->detect == q->depend)
21			return p;
22
23	return NULL;
24}
25
26
27void __init sort_iommu_table(struct iommu_table_entry *start,
28			     struct iommu_table_entry *finish) {
29
30	struct iommu_table_entry *p, *q, tmp;
31
32	for (p = start; p < finish; p++) {
33again:
34		q = find_dependents_of(start, finish, p);
35		/* We are bit sneaky here. We use the memory address to figure
36		 * out if the node we depend on is past our point, if so, swap.
37		 */
38		if (q > p) {
39			tmp = *p;
40			memmove(p, q, sizeof(*p));
41			*q = tmp;
42			goto again;
43		}
44	}
45
46}
47
48#ifdef DEBUG
49void __init check_iommu_entries(struct iommu_table_entry *start,
50				struct iommu_table_entry *finish)
51{
52	struct iommu_table_entry *p, *q, *x;
53
54	/* Simple cyclic dependency checker. */
55	for (p = start; p < finish; p++) {
56		q = find_dependents_of(start, finish, p);
57		x = find_dependents_of(start, finish, q);
58		if (p == x) {
59			printk(KERN_ERR "CYCLIC DEPENDENCY FOUND! %pS depends on %pS and vice-versa. BREAKING IT.\n",
60			       p->detect, q->detect);
61			/* Heavy handed way..*/
62			x->depend = 0;
63		}
64	}
65
66	for (p = start; p < finish; p++) {
67		q = find_dependents_of(p, finish, p);
68		if (q && q > p) {
69			printk(KERN_ERR "EXECUTION ORDER INVALID! %pS should be called before %pS!\n",
70			       p->detect, q->detect);
71		}
72	}
73}
74#else
75inline void check_iommu_entries(struct iommu_table_entry *start,
76				       struct iommu_table_entry *finish)
77{
78}
79#endif
80