Date: Thu, 18 Dec 1997 03:50:32 -0800 From: John-Mark Gurney <gurney_j@efn.org> To: FreeBSD Hackers <freebsd-hackers@freebsd.org> Subject: converting drivers to dynamic memory... Message-ID: <19971218035032.46460@hydrogen.nike.efn.org>
next in thread | raw e-mail | index | archive | help
well... one of the things that will need to be done in preperation for moving to a dynamic system which will be required by the bus/device code, we will need to eliminate ALL static datat that depends upon Ndevice to size itself. There are two ways that we can fix this problem. The first (and technically the best) is to be extend many of the calling functions to pass around a void * pointer that will point to that devices resources. Though this is technically best, it will require that most major parts of the kernel be significantly changes. The second solution is to continue to use the major/minor code scheme, but use a binary tree or a B-tree to obtain the private data. This can cause a performance impact if we use if for things like the sio, but this can be fixed by changing the interrupt interface. I think that we should go with the second solution as it will be initalially easier to do. I have B-tree code already writen, (I was writing it for another use in my bus/device code) which we could use to access this information. (Some people will say, why not linked lists, and then I will say, sio, I have 12 ports on my term server, plus you get better data density) On another note, how do people feel about more complex data structures becoming standard parts of the kernel. I think there are a number of places that using a more complex data structure would be a big win. I have code for both Fibonacci Heaps and B-tree's that just need some cleaning up to be generally useful. The code bloat would actually be quite small. The Fib heap code is under 3k, and the B-tree code is 4736 bytes, but this includes some debuging code (printing tree and checking that the tree is in order). Timings: Fibonacci heap (amortized): Make-Heap theta(1) Insert theta(1) Minimum theta(1) Extract-min O(lg n) Union theta(1) Decrease-key theta(1) Delete O(lg n) B-Tree (each node has between t - 1 and 2t -1 keys) Create O(1) Search O(t logt n) soon to be O(lg t * logt n) Insert " Delete " -- John-Mark Gurney Modem/FAX: +1 541 683 6954 Cu Networking P.O. Box 5693, 97405 Live in Peace, destroy Micro$oft, support free software, run FreeBSD
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?19971218035032.46460>