1/*******************************************************************************
2 *
3 * Module Name: nsalloc - Namespace allocation and deletion utilities
4 *              $Revision: 1.1.1.1 $
5 *
6 ******************************************************************************/
7
8/*
9 *  Copyright (C) 2000, 2001 R. Byron Moore
10 *
11 *  This program is free software; you can redistribute it and/or modify
12 *  it under the terms of the GNU General Public License as published by
13 *  the Free Software Foundation; either version 2 of the License, or
14 *  (at your option) any later version.
15 *
16 *  This program is distributed in the hope that it will be useful,
17 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
18 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
19 *  GNU General Public License for more details.
20 *
21 *  You should have received a copy of the GNU General Public License
22 *  along with this program; if not, write to the Free Software
23 *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
24 */
25
26
27#include "acpi.h"
28#include "acnamesp.h"
29#include "acinterp.h"
30
31
32#define _COMPONENT          ACPI_NAMESPACE
33	 MODULE_NAME         ("nsalloc")
34
35
36/*******************************************************************************
37 *
38 * FUNCTION:    Acpi_ns_create_node
39 *
40 * PARAMETERS:  Acpi_name       - Name of the new node
41 *
42 * RETURN:      None
43 *
44 * DESCRIPTION: Create a namespace node
45 *
46 ******************************************************************************/
47
48acpi_namespace_node *
49acpi_ns_create_node (
50	u32                     name)
51{
52	acpi_namespace_node     *node;
53
54
55	FUNCTION_TRACE ("Ns_create_node");
56
57
58	node = ACPI_MEM_CALLOCATE (sizeof (acpi_namespace_node));
59	if (!node) {
60		return_PTR (NULL);
61	}
62
63	ACPI_MEM_TRACKING (acpi_gbl_memory_lists[ACPI_MEM_LIST_NSNODE].total_allocated++);
64
65	node->data_type      = ACPI_DESC_TYPE_NAMED;
66	node->name           = name;
67	node->reference_count = 1;
68
69	return_PTR (node);
70}
71
72
73/*******************************************************************************
74 *
75 * FUNCTION:    Acpi_ns_delete_node
76 *
77 * PARAMETERS:  Node            - Node to be deleted
78 *
79 * RETURN:      None
80 *
81 * DESCRIPTION: Delete a namespace node
82 *
83 ******************************************************************************/
84
85void
86acpi_ns_delete_node (
87	acpi_namespace_node     *node)
88{
89	acpi_namespace_node     *parent_node;
90	acpi_namespace_node     *prev_node;
91	acpi_namespace_node     *next_node;
92
93
94	FUNCTION_TRACE_PTR ("Ns_delete_node", node);
95
96
97	parent_node = acpi_ns_get_parent_object (node);
98
99	prev_node = NULL;
100	next_node = parent_node->child;
101
102	while (next_node != node) {
103		prev_node = next_node;
104		next_node = prev_node->peer;
105	}
106
107	if (prev_node) {
108		prev_node->peer = next_node->peer;
109		if (next_node->flags & ANOBJ_END_OF_PEER_LIST) {
110			prev_node->flags |= ANOBJ_END_OF_PEER_LIST;
111		}
112	}
113	else {
114		parent_node->child = next_node->peer;
115	}
116
117
118	ACPI_MEM_TRACKING (acpi_gbl_memory_lists[ACPI_MEM_LIST_NSNODE].total_freed++);
119
120	/*
121	 * Detach an object if there is one
122	 */
123	if (node->object) {
124		acpi_ns_detach_object (node);
125	}
126
127	ACPI_MEM_FREE (node);
128	return_VOID;
129}
130
131
132/*******************************************************************************
133 *
134 * FUNCTION:    Acpi_ns_install_node
135 *
136 * PARAMETERS:  Walk_state      - Current state of the walk
137 *              Parent_node     - The parent of the new Node
138 *              Node            - The new Node to install
139 *              Type            - ACPI object type of the new Node
140 *
141 * RETURN:      None
142 *
143 * DESCRIPTION: Initialize a new entry within a namespace table.
144 *
145 ******************************************************************************/
146
147void
148acpi_ns_install_node (
149	acpi_walk_state         *walk_state,
150	acpi_namespace_node     *parent_node,   /* Parent */
151	acpi_namespace_node     *node,          /* New Child*/
152	acpi_object_type8       type)
153{
154	u16                     owner_id = TABLE_ID_DSDT;
155	acpi_namespace_node     *child_node;
156
157
158	FUNCTION_TRACE ("Ns_install_node");
159
160
161	/*
162	 * Get the owner ID from the Walk state
163	 * The owner ID is used to track table deletion and
164	 * deletion of objects created by methods
165	 */
166	if (walk_state) {
167		owner_id = walk_state->owner_id;
168	}
169
170
171	/* link the new entry into the parent and existing children */
172
173	/* TBD: Could be first, last, or alphabetic */
174
175	child_node = parent_node->child;
176	if (!child_node) {
177		parent_node->child = node;
178	}
179
180	else {
181		while (!(child_node->flags & ANOBJ_END_OF_PEER_LIST)) {
182			child_node = child_node->peer;
183		}
184
185		child_node->peer = node;
186
187		/* Clear end-of-list flag */
188
189		child_node->flags &= ~ANOBJ_END_OF_PEER_LIST;
190	}
191
192	/* Init the new entry */
193
194	node->owner_id  = owner_id;
195	node->flags     |= ANOBJ_END_OF_PEER_LIST;
196	node->peer      = parent_node;
197
198
199	/*
200	 * If adding a name with unknown type, or having to
201	 * add the region in order to define fields in it, we
202	 * have a forward reference.
203	 */
204	if ((ACPI_TYPE_ANY == type) ||
205		(INTERNAL_TYPE_FIELD_DEFN == type) ||
206		(INTERNAL_TYPE_BANK_FIELD_DEFN == type)) {
207		/*
208		 * We don't want to abort here, however!
209		 * We will fill in the actual type when the
210		 * real definition is found later.
211		 */
212		ACPI_DEBUG_PRINT ((ACPI_DB_INFO, "[%4.4s] is a forward reference\n",
213			(char*)&node->name));
214	}
215
216	/*
217	 * The Def_field_defn and Bank_field_defn cases are actually
218	 * looking up the Region in which the field will be defined
219	 */
220	if ((INTERNAL_TYPE_FIELD_DEFN == type) ||
221		(INTERNAL_TYPE_BANK_FIELD_DEFN == type)) {
222		type = ACPI_TYPE_REGION;
223	}
224
225	/*
226	 * Scope, Def_any, and Index_field_defn are bogus "types" which do
227	 * not actually have anything to do with the type of the name
228	 * being looked up.  Save any other value of Type as the type of
229	 * the entry.
230	 */
231	if ((type != INTERNAL_TYPE_SCOPE) &&
232		(type != INTERNAL_TYPE_DEF_ANY) &&
233		(type != INTERNAL_TYPE_INDEX_FIELD_DEFN)) {
234		node->type = (u8) type;
235	}
236
237	ACPI_DEBUG_PRINT ((ACPI_DB_NAMES, "%4.4s added to %p at %p\n",
238		(char*)&node->name, parent_node, node));
239
240	/*
241	 * Increment the reference count(s) of all parents up to
242	 * the root!
243	 */
244	while ((node = acpi_ns_get_parent_object (node)) != NULL) {
245		node->reference_count++;
246	}
247
248	return_VOID;
249}
250
251
252/*******************************************************************************
253 *
254 * FUNCTION:    Acpi_ns_delete_children
255 *
256 * PARAMETERS:  Parent_node     - Delete this objects children
257 *
258 * RETURN:      None.
259 *
260 * DESCRIPTION: Delete all children of the parent object. Deletes a
261 *              "scope".
262 *
263 ******************************************************************************/
264
265void
266acpi_ns_delete_children (
267	acpi_namespace_node     *parent_node)
268{
269	acpi_namespace_node     *child_node;
270	acpi_namespace_node     *next_node;
271	u8                      flags;
272
273
274	FUNCTION_TRACE_PTR ("Ns_delete_children", parent_node);
275
276
277	if (!parent_node) {
278		return_VOID;
279	}
280
281	/* If no children, all done! */
282
283	child_node = parent_node->child;
284	if (!child_node) {
285		return_VOID;
286	}
287
288	/*
289	 * Deallocate all children at this level
290	 */
291	do {
292		/* Get the things we need */
293
294		next_node   = child_node->peer;
295		flags       = child_node->flags;
296
297		/* Grandchildren should have all been deleted already */
298
299		if (child_node->child) {
300			ACPI_DEBUG_PRINT ((ACPI_DB_ERROR, "Found a grandchild! P=%p C=%p\n",
301				parent_node, child_node));
302		}
303
304		/* Now we can free this child object */
305
306		ACPI_MEM_TRACKING (acpi_gbl_memory_lists[ACPI_MEM_LIST_NSNODE].total_freed++);
307
308		ACPI_DEBUG_PRINT ((ACPI_DB_INFO, "Object %p, Remaining %X\n",
309			child_node, acpi_gbl_current_node_count));
310
311		/*
312		 * Detach an object if there is one, then free the child node
313		 */
314		acpi_ns_detach_object (child_node);
315		ACPI_MEM_FREE (child_node);
316
317		/* And move on to the next child in the list */
318
319		child_node = next_node;
320
321	} while (!(flags & ANOBJ_END_OF_PEER_LIST));
322
323
324	/* Clear the parent's child pointer */
325
326	parent_node->child = NULL;
327
328	return_VOID;
329}
330
331
332/*******************************************************************************
333 *
334 * FUNCTION:    Acpi_ns_delete_namespace_subtree
335 *
336 * PARAMETERS:  Parent_node     - Root of the subtree to be deleted
337 *
338 * RETURN:      None.
339 *
340 * DESCRIPTION: Delete a subtree of the namespace.  This includes all objects
341 *              stored within the subtree.  Scope tables are deleted also
342 *
343 ******************************************************************************/
344
345acpi_status
346acpi_ns_delete_namespace_subtree (
347	acpi_namespace_node     *parent_node)
348{
349	acpi_namespace_node     *child_node = NULL;
350	u32                     level = 1;
351
352
353	FUNCTION_TRACE ("Ns_delete_namespace_subtree");
354
355
356	if (!parent_node) {
357		return_ACPI_STATUS (AE_OK);
358	}
359
360	/*
361	 * Traverse the tree of objects until we bubble back up
362	 * to where we started.
363	 */
364	while (level > 0) {
365		/* Get the next node in this scope (NULL if none) */
366
367		child_node = acpi_ns_get_next_node (ACPI_TYPE_ANY, parent_node,
368				 child_node);
369		if (child_node) {
370			/* Found a child node - detach any attached object */
371
372			acpi_ns_detach_object (child_node);
373
374			/* Check if this node has any children */
375
376			if (acpi_ns_get_next_node (ACPI_TYPE_ANY, child_node, 0)) {
377				/*
378				 * There is at least one child of this node,
379				 * visit the node
380				 */
381				level++;
382				parent_node   = child_node;
383				child_node    = 0;
384			}
385		}
386
387		else {
388			/*
389			 * No more children of this parent node.
390			 * Move up to the grandparent.
391			 */
392			level--;
393
394			/*
395			 * Now delete all of the children of this parent
396			 * all at the same time.
397			 */
398			acpi_ns_delete_children (parent_node);
399
400			/* New "last child" is this parent node */
401
402			child_node = parent_node;
403
404			/* Move up the tree to the grandparent */
405
406			parent_node = acpi_ns_get_parent_object (parent_node);
407		}
408	}
409
410	return_ACPI_STATUS (AE_OK);
411}
412
413
414/*******************************************************************************
415 *
416 * FUNCTION:    Acpi_ns_remove_reference
417 *
418 * PARAMETERS:  Node           - Named node whose reference count is to be
419 *                               decremented
420 *
421 * RETURN:      None.
422 *
423 * DESCRIPTION: Remove a Node reference.  Decrements the reference count
424 *              of all parent Nodes up to the root.  Any node along
425 *              the way that reaches zero references is freed.
426 *
427 ******************************************************************************/
428
429static void
430acpi_ns_remove_reference (
431	acpi_namespace_node     *node)
432{
433	acpi_namespace_node     *next_node;
434
435
436	FUNCTION_ENTRY ();
437
438
439	/*
440	 * Decrement the reference count(s) of this node and all
441	 * nodes up to the root,  Delete anything with zero remaining references.
442	 */
443	next_node = node;
444	while (next_node) {
445		/* Decrement the reference count on this node*/
446
447		next_node->reference_count--;
448
449		/* Delete the node if no more references */
450
451		if (!next_node->reference_count) {
452			/* Delete all children and delete the node */
453
454			acpi_ns_delete_children (next_node);
455			acpi_ns_delete_node (next_node);
456		}
457
458		/* Move up to parent */
459
460		next_node = acpi_ns_get_parent_object (next_node);
461	}
462}
463
464
465/*******************************************************************************
466 *
467 * FUNCTION:    Acpi_ns_delete_namespace_by_owner
468 *
469 * PARAMETERS:  Owner_id    - All nodes with this owner will be deleted
470 *
471 * RETURN:      Status
472 *
473 * DESCRIPTION: Delete entries within the namespace that are owned by a
474 *              specific ID.  Used to delete entire ACPI tables.  All
475 *              reference counts are updated.
476 *
477 ******************************************************************************/
478
479acpi_status
480acpi_ns_delete_namespace_by_owner (
481	u16                     owner_id)
482{
483	acpi_namespace_node     *child_node;
484	u32                     level;
485	acpi_namespace_node     *parent_node;
486
487
488	FUNCTION_TRACE ("Ns_delete_namespace_by_owner");
489
490
491	parent_node = acpi_gbl_root_node;
492	child_node  = 0;
493	level       = 1;
494
495	/*
496	 * Traverse the tree of nodes until we bubble back up
497	 * to where we started.
498	 */
499	while (level > 0) {
500		/* Get the next node in this scope (NULL if none) */
501
502		child_node = acpi_ns_get_next_node (ACPI_TYPE_ANY, parent_node,
503				 child_node);
504		if (child_node) {
505			if (child_node->owner_id == owner_id) {
506				/* Found a child node - detach any attached object */
507
508				acpi_ns_detach_object (child_node);
509			}
510
511			/* Check if this node has any children */
512
513			if (acpi_ns_get_next_node (ACPI_TYPE_ANY, child_node, 0)) {
514				/*
515				 * There is at least one child of this node,
516				 * visit the node
517				 */
518				level++;
519				parent_node   = child_node;
520				child_node    = 0;
521			}
522
523			else if (child_node->owner_id == owner_id) {
524				acpi_ns_remove_reference (child_node);
525			}
526		}
527
528		else {
529			/*
530			 * No more children of this parent node.
531			 * Move up to the grandparent.
532			 */
533			level--;
534
535			if (level != 0) {
536				if (parent_node->owner_id == owner_id) {
537					acpi_ns_remove_reference (parent_node);
538				}
539			}
540
541			/* New "last child" is this parent node */
542
543			child_node = parent_node;
544
545			/* Move up the tree to the grandparent */
546
547			parent_node = acpi_ns_get_parent_object (parent_node);
548		}
549	}
550
551	return_ACPI_STATUS (AE_OK);
552}
553
554
555