xref: /openbmc/linux/drivers/acpi/acpica/nsalloc.c (revision f7c35abe)
1 /*******************************************************************************
2  *
3  * Module Name: nsalloc - Namespace allocation and deletion utilities
4  *
5  ******************************************************************************/
6 
7 /*
8  * Copyright (C) 2000 - 2017, Intel Corp.
9  * All rights reserved.
10  *
11  * Redistribution and use in source and binary forms, with or without
12  * modification, are permitted provided that the following conditions
13  * are met:
14  * 1. Redistributions of source code must retain the above copyright
15  *    notice, this list of conditions, and the following disclaimer,
16  *    without modification.
17  * 2. Redistributions in binary form must reproduce at minimum a disclaimer
18  *    substantially similar to the "NO WARRANTY" disclaimer below
19  *    ("Disclaimer") and any redistribution must be conditioned upon
20  *    including a substantially similar Disclaimer requirement for further
21  *    binary redistribution.
22  * 3. Neither the names of the above-listed copyright holders nor the names
23  *    of any contributors may be used to endorse or promote products derived
24  *    from this software without specific prior written permission.
25  *
26  * Alternatively, this software may be distributed under the terms of the
27  * GNU General Public License ("GPL") version 2 as published by the Free
28  * Software Foundation.
29  *
30  * NO WARRANTY
31  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
32  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
33  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR
34  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
35  * HOLDERS OR CONTRIBUTORS BE LIABLE FOR SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
36  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
37  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
38  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
39  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
40  * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
41  * POSSIBILITY OF SUCH DAMAGES.
42  */
43 
44 #include <acpi/acpi.h>
45 #include "accommon.h"
46 #include "acnamesp.h"
47 
48 #define _COMPONENT          ACPI_NAMESPACE
49 ACPI_MODULE_NAME("nsalloc")
50 
51 /*******************************************************************************
52  *
53  * FUNCTION:    acpi_ns_create_node
54  *
55  * PARAMETERS:  name            - Name of the new node (4 char ACPI name)
56  *
57  * RETURN:      New namespace node (Null on failure)
58  *
59  * DESCRIPTION: Create a namespace node
60  *
61  ******************************************************************************/
62 struct acpi_namespace_node *acpi_ns_create_node(u32 name)
63 {
64 	struct acpi_namespace_node *node;
65 #ifdef ACPI_DBG_TRACK_ALLOCATIONS
66 	u32 temp;
67 #endif
68 
69 	ACPI_FUNCTION_TRACE(ns_create_node);
70 
71 	node = acpi_os_acquire_object(acpi_gbl_namespace_cache);
72 	if (!node) {
73 		return_PTR(NULL);
74 	}
75 
76 	ACPI_MEM_TRACKING(acpi_gbl_ns_node_list->total_allocated++);
77 
78 #ifdef ACPI_DBG_TRACK_ALLOCATIONS
79 	temp = acpi_gbl_ns_node_list->total_allocated -
80 	    acpi_gbl_ns_node_list->total_freed;
81 	if (temp > acpi_gbl_ns_node_list->max_occupied) {
82 		acpi_gbl_ns_node_list->max_occupied = temp;
83 	}
84 #endif
85 
86 	node->name.integer = name;
87 	ACPI_SET_DESCRIPTOR_TYPE(node, ACPI_DESC_TYPE_NAMED);
88 	return_PTR(node);
89 }
90 
91 /*******************************************************************************
92  *
93  * FUNCTION:    acpi_ns_delete_node
94  *
95  * PARAMETERS:  node            - Node to be deleted
96  *
97  * RETURN:      None
98  *
99  * DESCRIPTION: Delete a namespace node. All node deletions must come through
100  *              here. Detaches any attached objects, including any attached
101  *              data. If a handler is associated with attached data, it is
102  *              invoked before the node is deleted.
103  *
104  ******************************************************************************/
105 
106 void acpi_ns_delete_node(struct acpi_namespace_node *node)
107 {
108 	union acpi_operand_object *obj_desc;
109 	union acpi_operand_object *next_desc;
110 
111 	ACPI_FUNCTION_NAME(ns_delete_node);
112 
113 	/* Detach an object if there is one */
114 
115 	acpi_ns_detach_object(node);
116 
117 	/*
118 	 * Delete an attached data object list if present (objects that were
119 	 * attached via acpi_attach_data). Note: After any normal object is
120 	 * detached above, the only possible remaining object(s) are data
121 	 * objects, in a linked list.
122 	 */
123 	obj_desc = node->object;
124 	while (obj_desc && (obj_desc->common.type == ACPI_TYPE_LOCAL_DATA)) {
125 
126 		/* Invoke the attached data deletion handler if present */
127 
128 		if (obj_desc->data.handler) {
129 			obj_desc->data.handler(node, obj_desc->data.pointer);
130 		}
131 
132 		next_desc = obj_desc->common.next_object;
133 		acpi_ut_remove_reference(obj_desc);
134 		obj_desc = next_desc;
135 	}
136 
137 	/* Special case for the statically allocated root node */
138 
139 	if (node == acpi_gbl_root_node) {
140 		return;
141 	}
142 
143 	/* Now we can delete the node */
144 
145 	(void)acpi_os_release_object(acpi_gbl_namespace_cache, node);
146 
147 	ACPI_MEM_TRACKING(acpi_gbl_ns_node_list->total_freed++);
148 	ACPI_DEBUG_PRINT((ACPI_DB_ALLOCATIONS, "Node %p, Remaining %X\n",
149 			  node, acpi_gbl_current_node_count));
150 }
151 
152 /*******************************************************************************
153  *
154  * FUNCTION:    acpi_ns_remove_node
155  *
156  * PARAMETERS:  node            - Node to be removed/deleted
157  *
158  * RETURN:      None
159  *
160  * DESCRIPTION: Remove (unlink) and delete a namespace node
161  *
162  ******************************************************************************/
163 
164 void acpi_ns_remove_node(struct acpi_namespace_node *node)
165 {
166 	struct acpi_namespace_node *parent_node;
167 	struct acpi_namespace_node *prev_node;
168 	struct acpi_namespace_node *next_node;
169 
170 	ACPI_FUNCTION_TRACE_PTR(ns_remove_node, node);
171 
172 	parent_node = node->parent;
173 
174 	prev_node = NULL;
175 	next_node = parent_node->child;
176 
177 	/* Find the node that is the previous peer in the parent's child list */
178 
179 	while (next_node != node) {
180 		prev_node = next_node;
181 		next_node = next_node->peer;
182 	}
183 
184 	if (prev_node) {
185 
186 		/* Node is not first child, unlink it */
187 
188 		prev_node->peer = node->peer;
189 	} else {
190 		/*
191 		 * Node is first child (has no previous peer).
192 		 * Link peer list to parent
193 		 */
194 		parent_node->child = node->peer;
195 	}
196 
197 	/* Delete the node and any attached objects */
198 
199 	acpi_ns_delete_node(node);
200 	return_VOID;
201 }
202 
203 /*******************************************************************************
204  *
205  * FUNCTION:    acpi_ns_install_node
206  *
207  * PARAMETERS:  walk_state      - Current state of the walk
208  *              parent_node     - The parent of the new Node
209  *              node            - The new Node to install
210  *              type            - ACPI object type of the new Node
211  *
212  * RETURN:      None
213  *
214  * DESCRIPTION: Initialize a new namespace node and install it amongst
215  *              its peers.
216  *
217  *              Note: Current namespace lookup is linear search. This appears
218  *              to be sufficient as namespace searches consume only a small
219  *              fraction of the execution time of the ACPI subsystem.
220  *
221  ******************************************************************************/
222 
223 void acpi_ns_install_node(struct acpi_walk_state *walk_state, struct acpi_namespace_node *parent_node,	/* Parent */
224 			  struct acpi_namespace_node *node,	/* New Child */
225 			  acpi_object_type type)
226 {
227 	acpi_owner_id owner_id = 0;
228 	struct acpi_namespace_node *child_node;
229 
230 	ACPI_FUNCTION_TRACE(ns_install_node);
231 
232 	if (walk_state) {
233 		/*
234 		 * Get the owner ID from the Walk state. The owner ID is used to
235 		 * track table deletion and deletion of objects created by methods.
236 		 */
237 		owner_id = walk_state->owner_id;
238 
239 		if ((walk_state->method_desc) &&
240 		    (parent_node != walk_state->method_node)) {
241 			/*
242 			 * A method is creating a new node that is not a child of the
243 			 * method (it is non-local). Mark the executing method as having
244 			 * modified the namespace. This is used for cleanup when the
245 			 * method exits.
246 			 */
247 			walk_state->method_desc->method.info_flags |=
248 			    ACPI_METHOD_MODIFIED_NAMESPACE;
249 		}
250 	}
251 
252 	/* Link the new entry into the parent and existing children */
253 
254 	node->peer = NULL;
255 	node->parent = parent_node;
256 	child_node = parent_node->child;
257 
258 	if (!child_node) {
259 		parent_node->child = node;
260 	} else {
261 		/* Add node to the end of the peer list */
262 
263 		while (child_node->peer) {
264 			child_node = child_node->peer;
265 		}
266 
267 		child_node->peer = node;
268 	}
269 
270 	/* Init the new entry */
271 
272 	node->owner_id = owner_id;
273 	node->type = (u8) type;
274 
275 	ACPI_DEBUG_PRINT((ACPI_DB_NAMES,
276 			  "%4.4s (%s) [Node %p Owner %X] added to %4.4s (%s) [Node %p]\n",
277 			  acpi_ut_get_node_name(node),
278 			  acpi_ut_get_type_name(node->type), node, owner_id,
279 			  acpi_ut_get_node_name(parent_node),
280 			  acpi_ut_get_type_name(parent_node->type),
281 			  parent_node));
282 
283 	return_VOID;
284 }
285 
286 /*******************************************************************************
287  *
288  * FUNCTION:    acpi_ns_delete_children
289  *
290  * PARAMETERS:  parent_node     - Delete this objects children
291  *
292  * RETURN:      None.
293  *
294  * DESCRIPTION: Delete all children of the parent object. In other words,
295  *              deletes a "scope".
296  *
297  ******************************************************************************/
298 
299 void acpi_ns_delete_children(struct acpi_namespace_node *parent_node)
300 {
301 	struct acpi_namespace_node *next_node;
302 	struct acpi_namespace_node *node_to_delete;
303 
304 	ACPI_FUNCTION_TRACE_PTR(ns_delete_children, parent_node);
305 
306 	if (!parent_node) {
307 		return_VOID;
308 	}
309 
310 	/* Deallocate all children at this level */
311 
312 	next_node = parent_node->child;
313 	while (next_node) {
314 
315 		/* Grandchildren should have all been deleted already */
316 
317 		if (next_node->child) {
318 			ACPI_ERROR((AE_INFO, "Found a grandchild! P=%p C=%p",
319 				    parent_node, next_node));
320 		}
321 
322 		/*
323 		 * Delete this child node and move on to the next child in the list.
324 		 * No need to unlink the node since we are deleting the entire branch.
325 		 */
326 		node_to_delete = next_node;
327 		next_node = next_node->peer;
328 		acpi_ns_delete_node(node_to_delete);
329 	};
330 
331 	/* Clear the parent's child pointer */
332 
333 	parent_node->child = NULL;
334 	return_VOID;
335 }
336 
337 /*******************************************************************************
338  *
339  * FUNCTION:    acpi_ns_delete_namespace_subtree
340  *
341  * PARAMETERS:  parent_node     - Root of the subtree to be deleted
342  *
343  * RETURN:      None.
344  *
345  * DESCRIPTION: Delete a subtree of the namespace. This includes all objects
346  *              stored within the subtree.
347  *
348  ******************************************************************************/
349 
350 void acpi_ns_delete_namespace_subtree(struct acpi_namespace_node *parent_node)
351 {
352 	struct acpi_namespace_node *child_node = NULL;
353 	u32 level = 1;
354 	acpi_status status;
355 
356 	ACPI_FUNCTION_TRACE(ns_delete_namespace_subtree);
357 
358 	if (!parent_node) {
359 		return_VOID;
360 	}
361 
362 	/* Lock namespace for possible update */
363 
364 	status = acpi_ut_acquire_mutex(ACPI_MTX_NAMESPACE);
365 	if (ACPI_FAILURE(status)) {
366 		return_VOID;
367 	}
368 
369 	/*
370 	 * Traverse the tree of objects until we bubble back up
371 	 * to where we started.
372 	 */
373 	while (level > 0) {
374 
375 		/* Get the next node in this scope (NULL if none) */
376 
377 		child_node = acpi_ns_get_next_node(parent_node, child_node);
378 		if (child_node) {
379 
380 			/* Found a child node - detach any attached object */
381 
382 			acpi_ns_detach_object(child_node);
383 
384 			/* Check if this node has any children */
385 
386 			if (child_node->child) {
387 				/*
388 				 * There is at least one child of this node,
389 				 * visit the node
390 				 */
391 				level++;
392 				parent_node = child_node;
393 				child_node = NULL;
394 			}
395 		} else {
396 			/*
397 			 * No more children of this parent node.
398 			 * Move up to the grandparent.
399 			 */
400 			level--;
401 
402 			/*
403 			 * Now delete all of the children of this parent
404 			 * all at the same time.
405 			 */
406 			acpi_ns_delete_children(parent_node);
407 
408 			/* New "last child" is this parent node */
409 
410 			child_node = parent_node;
411 
412 			/* Move up the tree to the grandparent */
413 
414 			parent_node = parent_node->parent;
415 		}
416 	}
417 
418 	(void)acpi_ut_release_mutex(ACPI_MTX_NAMESPACE);
419 	return_VOID;
420 }
421 
422 /*******************************************************************************
423  *
424  * FUNCTION:    acpi_ns_delete_namespace_by_owner
425  *
426  * PARAMETERS:  owner_id    - All nodes with this owner will be deleted
427  *
428  * RETURN:      Status
429  *
430  * DESCRIPTION: Delete entries within the namespace that are owned by a
431  *              specific ID. Used to delete entire ACPI tables. All
432  *              reference counts are updated.
433  *
434  * MUTEX:       Locks namespace during deletion walk.
435  *
436  ******************************************************************************/
437 
438 void acpi_ns_delete_namespace_by_owner(acpi_owner_id owner_id)
439 {
440 	struct acpi_namespace_node *child_node;
441 	struct acpi_namespace_node *deletion_node;
442 	struct acpi_namespace_node *parent_node;
443 	u32 level;
444 	acpi_status status;
445 
446 	ACPI_FUNCTION_TRACE_U32(ns_delete_namespace_by_owner, owner_id);
447 
448 	if (owner_id == 0) {
449 		return_VOID;
450 	}
451 
452 	/* Lock namespace for possible update */
453 
454 	status = acpi_ut_acquire_mutex(ACPI_MTX_NAMESPACE);
455 	if (ACPI_FAILURE(status)) {
456 		return_VOID;
457 	}
458 
459 	deletion_node = NULL;
460 	parent_node = acpi_gbl_root_node;
461 	child_node = NULL;
462 	level = 1;
463 
464 	/*
465 	 * Traverse the tree of nodes until we bubble back up
466 	 * to where we started.
467 	 */
468 	while (level > 0) {
469 		/*
470 		 * Get the next child of this parent node. When child_node is NULL,
471 		 * the first child of the parent is returned
472 		 */
473 		child_node = acpi_ns_get_next_node(parent_node, child_node);
474 
475 		if (deletion_node) {
476 			acpi_ns_delete_children(deletion_node);
477 			acpi_ns_remove_node(deletion_node);
478 			deletion_node = NULL;
479 		}
480 
481 		if (child_node) {
482 			if (child_node->owner_id == owner_id) {
483 
484 				/* Found a matching child node - detach any attached object */
485 
486 				acpi_ns_detach_object(child_node);
487 			}
488 
489 			/* Check if this node has any children */
490 
491 			if (child_node->child) {
492 				/*
493 				 * There is at least one child of this node,
494 				 * visit the node
495 				 */
496 				level++;
497 				parent_node = child_node;
498 				child_node = NULL;
499 			} else if (child_node->owner_id == owner_id) {
500 				deletion_node = child_node;
501 			}
502 		} else {
503 			/*
504 			 * No more children of this parent node.
505 			 * Move up to the grandparent.
506 			 */
507 			level--;
508 			if (level != 0) {
509 				if (parent_node->owner_id == owner_id) {
510 					deletion_node = parent_node;
511 				}
512 			}
513 
514 			/* New "last child" is this parent node */
515 
516 			child_node = parent_node;
517 
518 			/* Move up the tree to the grandparent */
519 
520 			parent_node = parent_node->parent;
521 		}
522 	}
523 
524 	(void)acpi_ut_release_mutex(ACPI_MTX_NAMESPACE);
525 	return_VOID;
526 }
527