Date: Wed, 10 Jan 1996 13:25:45 -0700 (MST) From: Terry Lambert <terry@lambert.org> To: hasty@rah.star-gate.com (Amancio Hasty Jr.) Cc: terry@lambert.org, freebsd-hackers@FreeBSD.org Subject: Re: PnP problem... Message-ID: <199601102025.NAA15319@phaeton.artisoft.com> In-Reply-To: <199601101946.LAA00916@rah.star-gate.com> from "Amancio Hasty Jr." at Jan 10, 96 11:46:05 am
next in thread | previous in thread | raw e-mail | index | archive | help
> Lets take this a step a time. In my case, I have a PnP motherboard. > > 1) disable all PnP > 2) probe all non-PnP cards > 3) Query PnP cards for where they may fit > 4) Do a topological sort to fit them all > > How am I supposed to know that I have a driver for a given PnP device? You don't care, in the general case. Non-PnP cards are probed before the sort because you can't cause them to be relocated. This give you a base set of per device configuration attributes for those devices which you recognize. In the PnP motherboard case, you disable non-PnP cards that you can't probe. In the non-PnP motherboard case, there is a finite risk that there will be non-PnP devices that you did not probe and therefore you will miss some per device configuration attributes and get screwed when you go to do PnP attribute assignment. Welcome to the wonderful world of ISA and reason #1 why there is no such thing as PnP for an ISA machine that doesn't have PnP extensions on the motherboard itself. Now when you go to add the PnP devices, you need to: 1) Determine the allocable per device configuration attributes for each device. This results in a fuzzy graph entry for the resorce utilization topology for the device. That is, each potential is equally valid, but exclusive of other potentials. 2) Perform a topologocal sort on the devices to choose non conflicting allocations for all devices. > Also do you care to elaborate on what is a "topological sort" and how > is applicable to our scenario? OK. Each graph entry for a device has a number of dimensions: one per attribute of the device. The DRQ, the IRQ, mapped memory regions, and port addresses. The graph entry can be considered to describe a set of n dimensional manifolds in an m dimensional space, where n <= m, m being the total allowable number of graph attributes per device. >From Sujal Patel's posting: | Each Logical Device can ask for: | up to 8 sets of I/O Ports | up to 2 IRQs | up to 2 DMA Channels | up to 4 Memory Regions | and countless other things.. Ignoring (for now) "countless" other things, we get a value for 'm' of 16. So what we have is a 16 dimensional space (we have not established domain or range on any dimension yet) in which we wish to fit some finite number (the number of logical PnP devices) of n dimensional manifolds (n<=16) with some 'k(d)',k(d)>=1, potential configurations (d is the number of devices we need to fit, k(d) is the number of poetential topologies per devices). With me so far? This is the topological equivalent of the traveling salesman problem (a 2 dimensional graph theory problem). The easiest method of accomplishing this is brute force, since we DON'T CARE if we get "the *optimal* soloution", all we care about is getting "*a* soloution". So we sort the device list by the number of potential configurations in any dimension, from "smallest domain" to "largest domain" to give preference to "hard to fit everything you want to fit into it" dimensions. This is a sort based on the toplogy of the problem when expressed as the mapping of manifolds. A topological sort. Then you start fitting devices on the basis of some abitrary measure of their "system criticality" until you are done. The problem may occur that you have too many devices to fit. OK. It means you have too many devices to fit. You are a bad person for plugging 5 GUS cards with 6 interrupts each into a machine that doesn't support more than 30 IRQ's. I agree that in an ideal world, you would probe a device after it is mapped because you know the driver that handles it by device ID. I would think this would be a rev 2.0 issue, since the data tables (as NetBSD has shown for PCI) can get quite large, and you want to be able to discard segments in the kernel that aren't being used if you plan on doing this (COFF or ELF format to allow seperability of integral kernel components from an already loaded kernel image). In our non-ideal world, you may end up with some devices mapped for which you don't have drivers available. For system critical devices, the correct soloution is using a VM86() to use BIOS to create drivers usable from protected mode without native drivers for the devices. In the very worst case, you will end up with devices that you have drivers for not being mapped in favor of devies that you don't have drivers for when you have too many devices (manifolds) to fit in the available system mappings (space) without overlap. Oh well. You will have this problem anyway. Unplug something, or allow disabling of device by ID in the boot process from a "boot -c" given a post sort conflict list. > Last but not least the steps you are outlining would probably work > well in Win95 because they have a way to remember which boot sequence > failed. In our case, we want to succeed the first time 8) Not necessarily. Why don't we want to log as well? All we need is two 16 bit counters which we alternately increment and guarantee are committed to disk. This allows 2^16 probes, probably more than are necessary for most GUS cards (maybe not all of them, though? 8-)). If we come back and the counters are one off from each other, we offer an option to "continue probing". We skip the probe of the highest numbered device as "destructive to a device we know to be in the system because of the hang and subsequent user reset of the machine". Terry Lambert terry@lambert.org --- Any opinions in this posting are my own and not those of my present or previous employers.
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?199601102025.NAA15319>