/* * nextpnr -- Next Generation Place and Route * * Copyright (C) 2018 Serge Bazanski * * Permission to use, copy, modify, and/or distribute this software for any * purpose with or without fee is hereby granted, provided that the above * copyright notice and this permission notice appear in all copies. * * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. * */ #ifndef QUADTREE_H #define QUADTREE_H // This file implements a quad tree used for committing 2D axis aligned // bounding boxes and then retrieving them by 2D point. NEXTPNR_NAMESPACE_BEGIN // A node of a QuadTree. Internal. template class QuadTreeNode { public: class BoundingBox { friend class QuadTreeNode; private: CoordinateT x0_, y0_, x1_, y1_; static constexpr float pinf = std::numeric_limits::infinity(); static constexpr float ninf = -std::numeric_limits::infinity(); public: // Standard constructor for a given (x0,y0), (x1,y1) bounding box // // @param x0 x coordinate of top-left corner of box // @param y0 y coordinate of top-left corner of box // @param x1 x coordinate of bottom-right corner of box // @param y1 y coordinate of bottom-right corner of box BoundingBox(CoordinateT x0, CoordinateT y0, CoordinateT x1, CoordinateT y1) : x0_(x0), y0_(y0), x1_(x1), y1_(y1) { } BoundingBox() : x0_(pinf), y0_(pinf), x1_(ninf), y1_(ninf) {} // Whether a bounding box contains a given points. // A point is defined to be in a bounding box when it's not lesser than // the lower coordinate or greater than the higher coordinate, eg: // A BoundingBox of x0: 20, y0: 30, x1: 100, y1: 130 fits the following // points: // [ (50, 50), (20, 50), (20, 30), (100, 130) ] inline bool contains(CoordinateT x, CoordinateT y) const { if (x < x0_ || x > x1_) return false; if (y < y0_ || y > y1_) return false; return true; } // Sort the bounding box coordinates. void fixup() { if (x1_ < x0_) std::swap(x0_, x1_); if (y1_ < y0_) std::swap(y0_, y1_); } CoordinateT x0() const { return x0_; } CoordinateT y0() const { return y0_; } CoordinateT x1() const { return x1_; } CoordinateT y1() const { return y1_; } void setX0(CoordinateT v) { x0_ = v; } void setY0(CoordinateT v) { y0_ = v; } void setX1(CoordinateT v) { x1_ = v; } void setY1(CoordinateT v) { y1_ = v; } void clear() { x0_ = pinf; y0_ = pinf; x1_ = ninf; y1_ = ninf; } CoordinateT w() const { return x1_ - x0_; } CoordinateT h() const { return y1_ - y0_; } }; private: // A pair of Element and BoundingBox that contains it. class BoundElement { friend class QuadTreeNode; private: BoundingBox bb_; ElementT elem_; public: BoundElement(BoundingBox bb, ElementT elem) : bb_(bb), elem_(elem) {} }; // The bounding box that this node describes. BoundingBox bound_; // How many elements should be contained in this node until it splits into // sub-nodes. const size_t max_elems_; // Four sub-nodes or nullptr if it hasn't split yet. std::unique_ptr[]> children_ = nullptr; // Coordinates of the split. // Anything < split_x is west. CoordinateT splitx_; // Anything < split_y is north. CoordinateT splity_; // Elements contained directly within this node and not part of children // nodes. std::vector elems_; // Depth at which this node is - root is at 0, first level at 1, etc. int depth_; // Checks whether a given bounding box fits within this node - used for // sanity checking on insertion. // @param b bounding box to check // @returns whether b fits in this node entirely bool fits(const BoundingBox &b) const { if (b.x0_ < bound_.x0_ || b.x0_ > bound_.x1_) { return false; } else if (b.x1_ < bound_.x0_ || b.x1_ > bound_.x1_) { return false; } else if (b.y0_ < bound_.y0_ || b.y0_ > bound_.y1_) { return false; } else if (b.y1_ < bound_.y0_ || b.y1_ > bound_.y1_) { return false; } return true; } // Used to describe one of 5 possible places an element can exist: // - the node itself (THIS) // - any of the 4 children nodes. enum Quadrant { THIS_NODE = -1, NW = 0, NE = 1, SW = 2, SE = 3 }; // Finds the quadrant to which a bounding box should go (if the node // is / were to be split). // @param b bounding box to check // @returns quadrant in which b belongs to if the node is were to be split Quadrant quadrant(const BoundingBox &b) const { if (children_ == nullptr) { return THIS_NODE; } bool west0 = b.x0_ < splitx_; bool west1 = b.x1_ < splitx_; bool north0 = b.y0_ < splity_; bool north1 = b.y1_ < splity_; if (west0 && west1 && north0 && north1) return NW; if (!west0 && !west1 && north0 && north1) return NE; if (west0 && west1 && !north0 && !north1) return SW; if (!west0 && !west1 && !north0 && !north1) return SE; return THIS_NODE; } // Checks whether this node should split. bool should_split() const { // The node shouldn't split if it's not large enough to merit it. if (elems_.size() < max_elems_) return false; // The node shouldn't split if its' level is too deep (this is true for // 100k+ entries, where the amount of splits causes us to lose // significant CPU time on traversing the tree, or worse yet causes a // stack overflow). if (depth_ > 5) return false; return true; } public: // Standard constructor for node. // @param b BoundingBox this node covers. // @param depth depth at which this node is in the tree // @max_elems how many elements should this node contain before it splits QuadTreeNode(BoundingBox b, int depth, size_t max_elems = 4) : bound_(b), max_elems_(max_elems), depth_(depth) {} // Disallow copies. QuadTreeNode(const QuadTreeNode &other) = delete; QuadTreeNode &operator=(const QuadTreeNode &other) = delete; // Allow moves. QuadTreeNode(QuadTreeNode &&other) : bound_(other.bound_), max_elems_(other.max_elems_), children_(std::move(other.children_)), splitx_(other.splitx_), splity_(other.splity_), elems_(std::move(other.elems_)), depth_(other.depth_) { other.children_ = nullptr; } QuadTreeNode &operator=(QuadTreeNode &&other) { if (this == &other) return *this; bound_ = other.bound_; max_elems_ = other.max_elems_; children_ = other.max_children_; children_ = other.children_; splitx_ = other.splitx_; splity_ = other.splity_; elems_ = std::move(other.elems_); depth_ = other.depth_; other.children_ = nullptr; return *this; } // Insert an element at a given bounding box. bool insert(const BoundingBox &k, ElementT v) { // Fail early if this BB doesn't fit us at all. if (!fits(k)) { return false; } // Do we have children? if (children_ != nullptr) { // Put the element either recursively into a child if it fits // entirely or keep it for ourselves if not. auto quad = quadrant(k); if (quad == THIS_NODE) { elems_.push_back(BoundElement(k, std::move(v))); } else { return children_[quad].insert(k, std::move(v)); } } else { // No children and not about to have any. if (!should_split()) { elems_.push_back(BoundElement(k, std::move(v))); return true; } // Splitting. Calculate the split point. splitx_ = (bound_.x1_ - bound_.x0_) / 2 + bound_.x0_; splity_ = (bound_.y1_ - bound_.y0_) / 2 + bound_.y0_; // Create the new children. children_ = decltype(children_)(new QuadTreeNode[4] { // Note: not using [NW] = QuadTreeNode because that seems to // crash g++ 7.3.0. /* NW */ QuadTreeNode(BoundingBox(bound_.x0_, bound_.y0_, splitx_, splity_), depth_ + 1, max_elems_), /* NE */ QuadTreeNode(BoundingBox(splitx_, bound_.y0_, bound_.x1_, splity_), depth_ + 1, max_elems_), /* SW */ QuadTreeNode(BoundingBox(bound_.x0_, splity_, splitx_, bound_.y1_), depth_ + 1, max_elems_), /* SE */ QuadTreeNode(BoundingBox(splitx_, splity_, bound_.x1_, bound_.y1_), depth_ + 1, max_elems_), }); // Move all elements to where they belong. auto it = elems_.begin(); while (it != elems_.end()) { auto quad = quadrant(it->bb_); if (quad != THIS_NODE) { // Move to one of the children. if (!children_[quad].insert(it->bb_, std::move(it->elem_))) return false; // Delete from ourselves. it = elems_.erase(it); } else { // Keep for ourselves. it++; } } // Insert the actual element now that we've split. return insert(k, std::move(v)); } return true; } // Dump a human-readable representation of the tree to stdout. void dump(int level) const { for (int i = 0; i < level; i++) printf(" "); printf("loc: % 3d % 3d % 3d % 3d\n", bound_.x0_, bound_.y0_, bound_.x1_, bound_.y1_); if (elems_.size() != 0) { for (int i = 0; i < level; i++) printf(" "); printf("elems: %zu\n", elems_.size()); } if (children_ != nullptr) { for (int i = 0; i < level; i++) printf(" "); printf("children:\n"); children_[NW].dump(level + 1); children_[NE].dump(level + 1); children_[SW].dump(level + 1); children_[SE].dump(level + 1); } } // Return count of BoundingBoxes/Elements contained. // @returns count of elements contained. size_t size() const { size_t res = elems_.size(); if (children_ != nullptr) { res += children_[NW].size(); res += children_[NE].size(); res += children_[SW].size(); res += children_[SE].size(); } return res; } // Retrieve elements whose bounding boxes cover the given coordinates. // // @param x X coordinate of points to query. // @param y Y coordinate of points to query. // @returns vector of found bounding boxes void get(CoordinateT x, CoordinateT y, std::vector &res) const { if (!bound_.contains(x, y)) return; for (const auto &elem : elems_) { const auto &bb = elem.bb_; if (bb.contains(x, y)) { res.push_back(elem.elem_); } } if (children_ != nullptr) { children_[NW].get(x, y, res); children_[NE].get(x, y, res); children_[SW].get(x, y, res); children_[SE].get(x, y, res); } } }; // User facing method to manage a quad tree. // // @param CoodinateT scalar type of the coordinate system - int, float, ... // @param ElementT type of the contained element. Must be movable or copiable. template class QuadTree { private: // Root of the tree. QuadTreeNode root_; public: // To let user create bounding boxes of the correct type. // Bounding boxes are composed of two 2D points, which designate their // top-left and bottom-right corners. All its' edges are axis aligned. using BoundingBox = typename QuadTreeNode::BoundingBox; // Standard constructor. // // @param b Bounding box of the entire tree - all committed elements must // fit within in. QuadTree(BoundingBox b) : root_(b, 0) {} // Inserts a new value at a given bounding box.e // BoundingBoxes are not deduplicated - if two are pushed with the same // coordinates, the first one will take precedence. // // @param k Bounding box at which to store value. // @param v Value at a given bounding box. // @returns Whether the insert was successful. bool insert(BoundingBox k, ElementT v) { k.fixup(); return root_.insert(k, v); } // Dump a human-readable representation of the tree to stdout. void dump() const { root_.dump(0); } // Return count of BoundingBoxes/Elements contained. // @returns count of elements contained. size_t size() const { return root_.size(); } // Retrieve elements whose bounding boxes cover the given coordinates. // // @param x X coordinate of points to query. // @param y Y coordinate of points to query. // @returns vector of found bounding boxes std::vector get(CoordinateT x, CoordinateT y) const { std::vector res; root_.get(x, y, res); return res; } }; NEXTPNR_NAMESPACE_END #endif ef='#n335'>335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 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 508 509 510 511 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 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 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 
/*
 *  acpi_tables.c - ACPI Boot-Time Table Parsing
 *
 *  Copyright (C) 2001 Paul Diefenbaugh <paul.s.diefenbaugh@intel.com>
 *
 * ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 *
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program; if not, write to the Free Software
 *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 *
 * ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 *
 */

#include <linux/config.h>
#include <linux/init.h>
#include <linux/kernel.h>
#include <linux/sched.h>
#include <linux/smp.h>
#include <linux/string.h>
#include <linux/types.h>
#include <linux/irq.h>
#include <linux/errno.h>
#include <linux/acpi.h>
#include <linux/bootmem.h>

#define PREFIX			"ACPI: "

#define ACPI_MAX_TABLES		256

static char *acpi_table_signatures[ACPI_TABLE_COUNT] = {
	[ACPI_TABLE_UNKNOWN]	= "????",
	[ACPI_APIC]		= "APIC",
	[ACPI_BOOT]		= "BOOT",
	[ACPI_DBGP]		= "DBGP",
	[ACPI_DSDT]		= "DSDT",
	[ACPI_ECDT]		= "ECDT",
	[ACPI_ETDT]		= "ETDT",
	[ACPI_FADT]		= "FACP",
	[ACPI_FACS]		= "FACS",
	[ACPI_OEMX]		= "OEM",
	[ACPI_PSDT]		= "PSDT",
	[ACPI_SBST]		= "SBST",
	[ACPI_SLIT]		= "SLIT",
	[ACPI_SPCR]		= "SPCR",
	[ACPI_SRAT]		= "SRAT",
	[ACPI_SSDT]		= "SSDT",
	[ACPI_SPMI]		= "SPMI",
	[ACPI_HPET]		= "HPET",
	[ACPI_MCFG]		= "MCFG",
};

static char *mps_inti_flags_polarity[] = { "dfl", "high", "res", "low" };
static char *mps_inti_flags_trigger[] = { "dfl", "edge", "res", "level" };

/* System Description Table (RSDT/XSDT) */
struct acpi_table_sdt {
	unsigned long		pa;
	enum acpi_table_id	id;
	unsigned long		size;
} __attribute__ ((packed));

static unsigned long		sdt_pa;		/* Physical Address */
static unsigned long		sdt_count;	/* Table count */

static struct acpi_table_sdt	sdt_entry[ACPI_MAX_TABLES];

void
acpi_table_print (
	struct acpi_table_header *header,
	unsigned long		phys_addr)
{
	char			*name = NULL;

	if (!header)
		return;

	/* Some table signatures aren't good table names */

	if (!strncmp((char *) &header->signature,
		acpi_table_signatures[ACPI_APIC],
		sizeof(header->signature))) {
		name = "MADT";
	}
	else if (!strncmp((char *) &header->signature,
		acpi_table_signatures[ACPI_FADT],
		sizeof(header->signature))) {
		name = "FADT";
	}
	else
		name = header->signature;

	printk(KERN_DEBUG PREFIX "%.4s (v%3.3d %6.6s %8.8s 0x%08x %.4s 0x%08x) @ 0x%p\n",
		name, header->revision, header->oem_id,
		header->oem_table_id, header->oem_revision,
		header->asl_compiler_id, header->asl_compiler_revision,
		(void *) phys_addr);
}


void
acpi_table_print_madt_entry (
	acpi_table_entry_header	*header)
{
	if (!header)
		return;

	switch (header->type) {

	case ACPI_MADT_LAPIC:
	{
		struct acpi_table_lapic *p =
			(struct acpi_table_lapic*) header;
		printk(KERN_INFO PREFIX "LAPIC (acpi_id[0x%02x] lapic_id[0x%02x] %s)\n",
			p->acpi_id, p->id, p->flags.enabled?"enabled":"disabled");
	}
		break;

	case ACPI_MADT_IOAPIC:
	{
		struct acpi_table_ioapic *p =
			(struct acpi_table_ioapic*) header;
		printk(KERN_INFO PREFIX "IOAPIC (id[0x%02x] address[0x%08x] gsi_base[%d])\n",
			p->id, p->address, p->global_irq_base);
	}
		break;

	case ACPI_MADT_INT_SRC_OVR:
	{
		struct acpi_table_int_src_ovr *p =
			(struct acpi_table_int_src_ovr*) header;
		printk(KERN_INFO PREFIX "INT_SRC_OVR (bus %d bus_irq %d global_irq %d %s %s)\n",
			p->bus, p->bus_irq, p->global_irq,
			mps_inti_flags_polarity[p->flags.polarity],
			mps_inti_flags_trigger[p->flags.trigger]);
		if(p->flags.reserved)
			printk(KERN_INFO PREFIX "INT_SRC_OVR unexpected reserved flags: 0x%x\n",
				p->flags.reserved);

	}
		break;

	case ACPI_MADT_NMI_SRC:
	{
		struct acpi_table_nmi_src *p =
			(struct acpi_table_nmi_src*) header;
		printk(KERN_INFO PREFIX "NMI_SRC (%s %s global_irq %d)\n",
			mps_inti_flags_polarity[p->flags.polarity],
			mps_inti_flags_trigger[p->flags.trigger], p->global_irq);
	}
		break;

	case ACPI_MADT_LAPIC_NMI:
	{
		struct acpi_table_lapic_nmi *p =
			(struct acpi_table_lapic_nmi*) header;
		printk(KERN_INFO PREFIX "LAPIC_NMI (acpi_id[0x%02x] %s %s lint[0x%x])\n",
			p->acpi_id,
			mps_inti_flags_polarity[p->flags.polarity],
			mps_inti_flags_trigger[p->flags.trigger], p->lint);
	}
		break;

	case ACPI_MADT_LAPIC_ADDR_OVR:
	{
		struct acpi_table_lapic_addr_ovr *p =
			(struct acpi_table_lapic_addr_ovr*) header;
		printk(KERN_INFO PREFIX "LAPIC_ADDR_OVR (address[%p])\n",
			(void *) (unsigned long) p->address);
	}
		break;

	case ACPI_MADT_IOSAPIC:
	{
		struct acpi_table_iosapic *p =
			(struct acpi_table_iosapic*) header;
		printk(KERN_INFO PREFIX "IOSAPIC (id[0x%x] address[%p] gsi_base[%d])\n",
			p->id, (void *) (unsigned long) p->address, p->global_irq_base);
	}
		break;

	case ACPI_MADT_LSAPIC:
	{
		struct acpi_table_lsapic *p =
			(struct acpi_table_lsapic*) header;
		printk(KERN_INFO PREFIX "LSAPIC (acpi_id[0x%02x] lsapic_id[0x%02x] lsapic_eid[0x%02x] %s)\n",
			p->acpi_id, p->id, p->eid, p->flags.enabled?"enabled":"disabled");
	}
		break;

	case ACPI_MADT_PLAT_INT_SRC:
	{
		struct acpi_table_plat_int_src *p =
			(struct acpi_table_plat_int_src*) header;
		printk(KERN_INFO PREFIX "PLAT_INT_SRC (%s %s type[0x%x] id[0x%04x] eid[0x%x] iosapic_vector[0x%x] global_irq[0x%x]\n",
			mps_inti_flags_polarity[p->flags.polarity],
			mps_inti_flags_trigger[p->flags.trigger],
			p->type, p->id, p->eid, p->iosapic_vector, p->global_irq);
	}
		break;

	default:
		printk(KERN_WARNING PREFIX "Found unsupported MADT entry (type = 0x%x)\n",
			header->type);
		break;
	}
}


static int
acpi_table_compute_checksum (
	void			*table_pointer,
	unsigned long		length)
{
	u8			*p = (u8 *) table_pointer;
	unsigned long		remains = length;
	unsigned long		sum = 0;

	if (!p || !length)
		return -EINVAL;

	while (remains--)
		sum += *p++;

	return (sum & 0xFF);
}

/*
 * acpi_get_table_header_early()
 * for acpi_blacklisted(), acpi_table_get_sdt()
 */
int __init
acpi_get_table_header_early (
	enum acpi_table_id	id,
	struct acpi_table_header **header)
{
	unsigned int i;
	enum acpi_table_id temp_id;

	/* DSDT is different from the rest */
	if (id == ACPI_DSDT)
		temp_id = ACPI_FADT;
	else
		temp_id = id;

	/* Locate the table. */

	for (i = 0; i < sdt_count; i++) {
		if (sdt_entry[i].id != temp_id)
			continue;
		*header = (void *)
			__acpi_map_table(sdt_entry[i].pa, sdt_entry[i].size);
		if (!*header) {
			printk(KERN_WARNING PREFIX "Unable to map %s\n",
			       acpi_table_signatures[temp_id]);
			return -ENODEV;
		}
		break;
	}

	if (!*header) {
		printk(KERN_WARNING PREFIX "%s not present\n",
		       acpi_table_signatures[id]);
		return -ENODEV;
	}

	/* Map the DSDT header via the pointer in the FADT */
	if (id == ACPI_DSDT) {
		struct fadt_descriptor_rev2 *fadt = (struct fadt_descriptor_rev2 *) *header;

		if (fadt->revision == 3 && fadt->Xdsdt) {
			*header = (void *) __acpi_map_table(fadt->Xdsdt,
					sizeof(struct acpi_table_header));
		} else if (fadt->V1_dsdt) {
			*header = (void *) __acpi_map_table(fadt->V1_dsdt,
					sizeof(struct acpi_table_header));
		} else
			*header = NULL;

		if (!*header) {
			printk(KERN_WARNING PREFIX "Unable to map DSDT\n");
			return -ENODEV;
		}
	}

	return 0;
}
	 

int __init
acpi_table_parse_madt_family (
	enum acpi_table_id	id,
	unsigned long		madt_size,
	int			entry_id,
	acpi_madt_entry_handler	handler,
	unsigned int		max_entries)
{
	void			*madt = NULL;
	acpi_table_entry_header	*entry;
	unsigned int		count = 0;
	unsigned long		madt_end;
	unsigned int		i;

	if (!handler)
		return -EINVAL;

	/* Locate the MADT (if exists). There should only be one. */

	for (i = 0; i < sdt_count; i++) {
		if (sdt_entry[i].id != id)
			continue;
		madt = (void *)
			__acpi_map_table(sdt_entry[i].pa, sdt_entry[i].size);
		if (!madt) {
			printk(KERN_WARNING PREFIX "Unable to map %s\n",
			       acpi_table_signatures[id]);
			return -ENODEV;
		}
		break;
	}

	if (!madt) {
		printk(KERN_WARNING PREFIX "%s not present\n",
		       acpi_table_signatures[id]);
		return -ENODEV;
	}

	madt_end = (unsigned long) madt + sdt_entry[i].size;

	/* Parse all entries looking for a match. */

	entry = (acpi_table_entry_header *)
		((unsigned long) madt + madt_size);

	while (((unsigned long) entry) + sizeof(acpi_table_entry_header) < madt_end) {
		if (entry->type == entry_id &&
		    (!max_entries || count++ < max_entries))
			if (handler(entry, madt_end))
				return -EINVAL;

		entry = (acpi_table_entry_header *)
			((unsigned long) entry + entry->length);
	}
	if (max_entries && count > max_entries) {
		printk(KERN_WARNING PREFIX "[%s:0x%02x] ignored %i entries of "
		       "%i found\n", acpi_table_signatures[id], entry_id,
		       count - max_entries, count);
	}

	return count;
}


int __init
acpi_table_parse_madt (
	enum acpi_madt_entry_id	id,
	acpi_madt_entry_handler	handler,
	unsigned int max_entries)
{
	return acpi_table_parse_madt_family(ACPI_APIC, sizeof(struct acpi_table_madt),
					    id, handler, max_entries);
}


int __init
acpi_table_parse (
	enum acpi_table_id	id,
	acpi_table_handler	handler)
{
	int			count = 0;
	unsigned int		i = 0;

	if (!handler)
		return -EINVAL;

	for (i = 0; i < sdt_count; i++) {
		if (sdt_entry[i].id != id)
			continue;
		count++;
		if (count == 1)
			handler(sdt_entry[i].pa, sdt_entry[i].size);

		else
			printk(KERN_WARNING PREFIX "%d duplicate %s table ignored.\n",
				count, acpi_table_signatures[id]);
	}

	return count;
}


static int __init
acpi_table_get_sdt (
	struct acpi_table_rsdp	*rsdp)
{
	struct acpi_table_header *header = NULL;
	unsigned int		i, id = 0;

	if (!rsdp)
		return -EINVAL;

	/* First check XSDT (but only on ACPI 2.0-compatible systems) */

	if ((rsdp->revision >= 2) &&
		(((struct acpi20_table_rsdp*)rsdp)->xsdt_address)) {
			
		struct acpi_table_xsdt	*mapped_xsdt = NULL;

		sdt_pa = ((struct acpi20_table_rsdp*)rsdp)->xsdt_address;

		/* map in just the header */
		header = (struct acpi_table_header *)
			__acpi_map_table(sdt_pa, sizeof(struct acpi_table_header));

		if (!header) {
			printk(KERN_WARNING PREFIX "Unable to map XSDT header\n");
			return -ENODEV;
		}

		/* remap in the entire table before processing */
		mapped_xsdt = (struct acpi_table_xsdt *)
			__acpi_map_table(sdt_pa, header->length);
		if (!mapped_xsdt) {
			printk(KERN_WARNING PREFIX "Unable to map XSDT\n");
			return -ENODEV;
		}
		header = &mapped_xsdt->header;

		if (strncmp(header->signature, "XSDT", 4)) {