/* drmP.h -- Private header for Direct Rendering Manager -*- c -*- * Created: Mon Jan 4 10:05:05 1999 by faith@precisioninsight.com * Revised: Tue Oct 12 08:51:07 1999 by faith@precisioninsight.com * * Copyright 1999 Precision Insight, Inc., Cedar Park, Texas. * All rights reserved. * * Permission is hereby granted, free of charge, to any person obtaining a * copy of this software and associated documentation files (the "Software"), * to deal in the Software without restriction, including without limitation * the rights to use, copy, modify, merge, publish, distribute, sublicense, * and/or sell copies of the Software, and to permit persons to whom the * Software is furnished to do so, subject to the following conditions: * * The above copyright notice and this permission notice (including the next * paragraph) shall be included in all copies or substantial portions of the * Software. * * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL * PRECISION INSIGHT AND/OR ITS SUPPLIERS BE LIABLE FOR ANY CLAIM, DAMAGES OR * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER * DEALINGS IN THE SOFTWARE. * * $PI: xc/programs/Xserver/hw/xfree86/os-support/linux/drm/kernel/drmP.h,v 1.58 1999/08/30 13:05:00 faith Exp $ * $XFree86: xc/programs/Xserver/hw/xfree86/os-support/bsd/drm/kernel/drmP.h,v 1.1 2000/06/17 00:03:28 martin Exp $ * */ #ifndef _DRM_P_H_ #define _DRM_P_H_ #ifdef _KERNEL #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #if __FreeBSD_version >= 500005 #include #endif #if __FreeBSD_version >= 500006 #define DRM_AGP #endif #ifdef DRM_AGP #include #endif #include "drm.h" typedef u_int32_t atomic_t; typedef u_int32_t cycles_t; typedef u_int32_t spinlock_t; #define atomic_set(p, v) (*(p) = (v)) #define atomic_read(p) (*(p)) #define atomic_inc(p) atomic_add_int(p, 1) #define atomic_dec(p) atomic_subtract_int(p, 1) #define atomic_add(n, p) atomic_add_int(p, n) #define atomic_sub(n, p) atomic_subtract_int(p, n) /* Fake this */ static __inline u_int32_t test_and_set_bit(int b, volatile u_int32_t *p) { int s = splhigh(); u_int32_t m = 1<> 5), 1 << (b & 0x1f)); } static __inline void set_bit(int b, volatile u_int32_t *p) { atomic_set_int(p + (b >> 5), 1 << (b & 0x1f)); } static __inline int test_bit(int b, volatile u_int32_t *p) { return p[b >> 5] & (1 << (b & 0x1f)); } static __inline int find_first_zero_bit(volatile u_int32_t *p, int max) { int b; for (b = 0; b < max; b += 32) { if (p[b >> 5] != ~0) { for (;;) { if ((p[b >> 5] & (1 << (b & 0x1f))) == 0) return b; b++; } } } return max; } #define spldrm() spltty() #define memset(p, v, s) bzero(p, s) /* * Fake out the module macros for versions of FreeBSD where they don't * exist. */ #if __FreeBSD_version < 500002 #define MODULE_VERSION(a,b) struct __hack #define MODULE_DEPEND(a,b,c,d,e) struct __hack #endif #define DRM_DEBUG_CODE 2 /* Include debugging code (if > 1, then also include looping detection. */ #define DRM_DMA_HISTOGRAM 1 /* Make histogram of DMA latency. */ #define DRM_HASH_SIZE 16 /* Size of key hash table */ #define DRM_KERNEL_CONTEXT 0 /* Change drm_resctx if changed */ #define DRM_RESERVED_CONTEXTS 1 /* Change drm_resctx if changed */ #define DRM_LOOPING_LIMIT 5000000 #define DRM_BSZ 1024 /* Buffer size for /dev/drm? output */ #define DRM_TIME_SLICE (hz/20) /* Time slice for GLXContexts */ #define DRM_LOCK_SLICE 1 /* Time slice for lock, in jiffies */ #define DRM_FLAG_DEBUG 0x01 #define DRM_FLAG_NOCTX 0x02 #define DRM_MEM_DMA 0 #define DRM_MEM_SAREA 1 #define DRM_MEM_DRIVER 2 #define DRM_MEM_MAGIC 3 #define DRM_MEM_IOCTLS 4 #define DRM_MEM_MAPS 5 #define DRM_MEM_VMAS 6 #define DRM_MEM_BUFS 7 #define DRM_MEM_SEGS 8 #define DRM_MEM_PAGES 9 #define DRM_MEM_FILES 10 #define DRM_MEM_QUEUES 11 #define DRM_MEM_CMDS 12 #define DRM_MEM_MAPPINGS 13 #define DRM_MEM_BUFLISTS 14 #define DRM_MEM_AGPLISTS 15 #define DRM_MEM_TOTALAGP 16 #define DRM_MEM_BOUNDAGP 17 #define DRM_MEM_CTXBITMAP 18 #define DRM_MAX_CTXBITMAP (PAGE_SIZE * 8) /* Backward compatibility section */ #ifndef _PAGE_PWT /* The name of _PAGE_WT was changed to _PAGE_PWT in Linux 2.2.6 */ #define _PAGE_PWT _PAGE_WT #endif #define __drm_dummy_lock(lock) (*(__volatile__ unsigned int *)lock) #define _DRM_CAS(lock,old,new,__ret) \ do { \ int __dummy; /* Can't mark eax as clobbered */ \ __asm__ __volatile__( \ "lock ; cmpxchg %4,%1\n\t" \ "setnz %0" \ : "=d" (__ret), \ "=m" (__drm_dummy_lock(lock)), \ "=a" (__dummy) \ : "2" (old), \ "r" (new)); \ } while (0) /* Macros to make printk easier */ #define DRM_ERROR(fmt, arg...) \ printf("error: " "[" DRM_NAME ":" __FUNCTION__ "] *ERROR* " fmt , ##arg) #define DRM_MEM_ERROR(area, fmt, arg...) \ printf("error: " "[" DRM_NAME ":" __FUNCTION__ ":%s] *ERROR* " fmt , \ drm_mem_stats[area].name , ##arg) #define DRM_INFO(fmt, arg...) printf("info: " "[" DRM_NAME "] " fmt , ##arg) #if DRM_DEBUG_CODE #define DRM_DEBUG(fmt, arg...) \ do { \ if (drm_flags&DRM_FLAG_DEBUG) \ printf("[" DRM_NAME ":" __FUNCTION__ "] " fmt , \ ##arg); \ } while (0) #else #define DRM_DEBUG(fmt, arg...) do { } while (0) #endif #define DRM_PROC_LIMIT (PAGE_SIZE-80) #define DRM_SYSCTL_PRINT(fmt, arg...) \ snprintf(buf, sizeof(buf), fmt, ##arg); \ error = SYSCTL_OUT(req, buf, strlen(buf)); \ if (error) return error; #define DRM_SYSCTL_PRINT_RET(ret, fmt, arg...) \ snprintf(buf, sizeof(buf), fmt, ##arg); \ error = SYSCTL_OUT(req, buf, strlen(buf)); \ if (error) { ret; return error; } /* Internal types and structures */ #define DRM_ARRAY_SIZE(x) (sizeof(x)/sizeof(x[0])) #define DRM_MIN(a,b) ((a)<(b)?(a):(b)) #define DRM_MAX(a,b) ((a)>(b)?(a):(b)) #define DRM_LEFTCOUNT(x) (((x)->rp + (x)->count - (x)->wp) % ((x)->count + 1)) #define DRM_BUFCOUNT(x) ((x)->count - DRM_LEFTCOUNT(x)) #define DRM_WAITCOUNT(dev,idx) DRM_BUFCOUNT(&dev->queuelist[idx]->waitlist) typedef struct drm_ioctl_desc { d_ioctl_t *func; int auth_needed; int root_only; } drm_ioctl_desc_t; typedef struct drm_devstate { pid_t owner; /* X server pid holding x_lock */ } drm_devstate_t; typedef struct drm_magic_entry { drm_magic_t magic; struct drm_file *priv; struct drm_magic_entry *next; } drm_magic_entry_t; typedef struct drm_magic_head { struct drm_magic_entry *head; struct drm_magic_entry *tail; } drm_magic_head_t; typedef struct drm_vma_entry { struct vm_area_struct *vma; struct drm_vma_entry *next; pid_t pid; } drm_vma_entry_t; typedef struct drm_buf { int idx; /* Index into master buflist */ int total; /* Buffer size */ int order; /* log-base-2(total) */ int used; /* Amount of buffer in use (for DMA) */ unsigned long offset; /* Byte offset (used internally) */ void *address; /* Address of buffer */ unsigned long bus_address; /* Bus address of buffer */ struct drm_buf *next; /* Kernel-only: used for free list */ __volatile__ int waiting; /* On kernel DMA queue */ __volatile__ int pending; /* On hardware DMA queue */ int dma_wait; /* Processes waiting */ pid_t pid; /* PID of holding process */ int context; /* Kernel queue for this buffer */ int while_locked;/* Dispatch this buffer while locked */ enum { DRM_LIST_NONE = 0, DRM_LIST_FREE = 1, DRM_LIST_WAIT = 2, DRM_LIST_PEND = 3, DRM_LIST_PRIO = 4, DRM_LIST_RECLAIM = 5 } list; /* Which list we're on */ void *dev_private; int dev_priv_size; #if DRM_DMA_HISTOGRAM struct timespec time_queued; /* Queued to kernel DMA queue */ struct timespec time_dispatched; /* Dispatched to hardware */ struct timespec time_completed; /* Completed by hardware */ struct timespec time_freed; /* Back on freelist */ #endif } drm_buf_t; #if DRM_DMA_HISTOGRAM #define DRM_DMA_HISTOGRAM_SLOTS 9 #define DRM_DMA_HISTOGRAM_INITIAL 10 #define DRM_DMA_HISTOGRAM_NEXT(current) ((current)*10) typedef struct drm_histogram { atomic_t total; atomic_t queued_to_dispatched[DRM_DMA_HISTOGRAM_SLOTS]; atomic_t dispatched_to_completed[DRM_DMA_HISTOGRAM_SLOTS]; atomic_t completed_to_freed[DRM_DMA_HISTOGRAM_SLOTS]; atomic_t queued_to_completed[DRM_DMA_HISTOGRAM_SLOTS]; atomic_t queued_to_freed[DRM_DMA_HISTOGRAM_SLOTS]; atomic_t dma[DRM_DMA_HISTOGRAM_SLOTS]; atomic_t schedule[DRM_DMA_HISTOGRAM_SLOTS]; atomic_t ctx[DRM_DMA_HISTOGRAM_SLOTS]; atomic_t lacq[DRM_DMA_HISTOGRAM_SLOTS]; atomic_t lhld[DRM_DMA_HISTOGRAM_SLOTS]; } drm_histogram_t; #endif /* bufs is one longer than it has to be */ typedef struct drm_waitlist { int count; /* Number of possible buffers */ drm_buf_t **bufs; /* List of pointers to buffers */ drm_buf_t **rp; /* Read pointer */ drm_buf_t **wp; /* Write pointer */ drm_buf_t **end; /* End pointer */ spinlock_t read_lock; spinlock_t write_lock; } drm_waitlist_t; typedef struct drm_freelist { int initialized; /* Freelist in use */ atomic_t count; /* Number of free buffers */ drm_buf_t *next; /* End pointer */ int waiting; /* Processes waiting on free bufs */ int low_mark; /* Low water mark */ int high_mark; /* High water mark */ atomic_t wfh; /* If waiting for high mark */ } drm_freelist_t; typedef struct drm_buf_entry { int buf_size; int buf_count; drm_buf_t *buflist; int seg_count; int page_order; unsigned long *seglist; drm_freelist_t freelist; } drm_buf_entry_t; typedef struct drm_hw_lock { __volatile__ unsigned int lock; char padding[60]; /* Pad to cache line */ } drm_hw_lock_t; typedef TAILQ_HEAD(drm_file_list, drm_file) drm_file_list_t; typedef struct drm_file { TAILQ_ENTRY(drm_file) link; int authenticated; int minor; pid_t pid; uid_t uid; int refs; drm_magic_t magic; unsigned long ioctl_count; struct drm_device *devXX; } drm_file_t; typedef struct drm_queue { atomic_t use_count; /* Outstanding uses (+1) */ atomic_t finalization; /* Finalization in progress */ atomic_t block_count; /* Count of processes waiting */ atomic_t block_read; /* Queue blocked for reads */ int read_queue; /* Processes waiting on block_read */ atomic_t block_write; /* Queue blocked for writes */ int write_queue; /* Processes waiting on block_write */ atomic_t total_queued; /* Total queued statistic */ atomic_t total_flushed;/* Total flushes statistic */ atomic_t total_locks; /* Total locks statistics */ drm_ctx_flags_t flags; /* Context preserving and 2D-only */ drm_waitlist_t waitlist; /* Pending buffers */ int flush_queue; /* Processes waiting until flush */ } drm_queue_t; typedef struct drm_lock_data { drm_hw_lock_t *hw_lock; /* Hardware lock */ pid_t pid; /* PID of lock holder (0=kernel) */ int lock_queue; /* Queue of blocked processes */ unsigned long lock_time; /* Time of last lock in jiffies */ } drm_lock_data_t; typedef struct drm_device_dma { /* Performance Counters */ atomic_t total_prio; /* Total DRM_DMA_PRIORITY */ atomic_t total_bytes; /* Total bytes DMA'd */ atomic_t total_dmas; /* Total DMA buffers dispatched */ atomic_t total_missed_dma; /* Missed drm_do_dma */ atomic_t total_missed_lock; /* Missed lock in drm_do_dma */ atomic_t total_missed_free; /* Missed drm_free_this_buffer */ atomic_t total_missed_sched;/* Missed drm_dma_schedule */ atomic_t total_tried; /* Tried next_buffer */ atomic_t total_hit; /* Sent next_buffer */ atomic_t total_lost; /* Lost interrupt */ drm_buf_entry_t bufs[DRM_MAX_ORDER+1]; int buf_count; drm_buf_t **buflist; /* Vector of pointers info bufs */ int seg_count; int page_count; vm_offset_t *pagelist; unsigned long byte_count; enum { _DRM_DMA_USE_AGP = 0x01 } flags; /* DMA support */ drm_buf_t *this_buffer; /* Buffer being sent */ drm_buf_t *next_buffer; /* Selected buffer to send */ drm_queue_t *next_queue; /* Queue from which buffer selected*/ int waiting; /* Processes waiting on free bufs */ } drm_device_dma_t; #ifdef DRM_AGP typedef struct drm_agp_mem { void *handle; unsigned long bound; /* address */ int pages; struct drm_agp_mem *prev; struct drm_agp_mem *next; } drm_agp_mem_t; typedef struct drm_agp_head { device_t agpdev; struct agp_info info; const char *chipset; drm_agp_mem_t *memory; unsigned long mode; int enabled; int acquired; unsigned long base; int agp_mtrr; } drm_agp_head_t; #endif typedef struct drm_device { const char *name; /* Simple driver name */ char *unique; /* Unique identifier: e.g., busid */ int unique_len; /* Length of unique field */ device_t device; /* Device instance from newbus */ dev_t devnode; /* Device number for mknod */ char *devname; /* For /proc/interrupts */ int blocked; /* Blocked due to VC switch? */ int flags; /* Flags to open(2) */ int writable; /* Opened with FWRITE */ struct proc_dir_entry *root; /* Root for this device's entries */ /* Locks */ struct simplelock count_lock; /* For inuse, open_count, buf_use */ struct lock dev_lock; /* For others */ /* Usage Counters */ int open_count; /* Outstanding files open */ atomic_t ioctl_count; /* Outstanding IOCTLs pending */ atomic_t vma_count; /* Outstanding vma areas open */ int buf_use; /* Buffers in use -- cannot alloc */ atomic_t buf_alloc; /* Buffer allocation in progress */ /* Performance Counters */ atomic_t total_open; atomic_t total_close; atomic_t total_ioctl; atomic_t total_irq; /* Total interruptions */ atomic_t total_ctx; /* Total context switches */ atomic_t total_locks; atomic_t total_unlocks; atomic_t total_contends; atomic_t total_sleeps; /* Authentication */ drm_file_list_t files; drm_magic_head_t magiclist[DRM_HASH_SIZE]; /* Memory management */ drm_map_t **maplist; /* Vector of pointers to regions */ int map_count; /* Number of mappable regions */ drm_vma_entry_t *vmalist; /* List of vmas (for debugging) */ drm_lock_data_t lock; /* Information on hardware lock */ /* DMA queues (contexts) */ int queue_count; /* Number of active DMA queues */ int queue_reserved; /* Number of reserved DMA queues */ int queue_slots; /* Actual length of queuelist */ drm_queue_t **queuelist; /* Vector of pointers to DMA queues */ drm_device_dma_t *dma; /* Optional pointer for DMA support */ /* Context support */ struct resource *irq; /* Interrupt used by board */ void *irqh; /* Handle from bus_setup_intr */ __volatile__ int context_flag; /* Context swapping flag */ __volatile__ int interrupt_flag;/* Interruption handler flag */ __volatile__ int dma_flag; /* DMA dispatch flag */ struct callout timer; /* Timer for delaying ctx switch */ int context_wait; /* Processes waiting on ctx switch */ int last_checked; /* Last context checked for DMA */ int last_context; /* Last current context */ int last_switch; /* Time at last context switch */ #if __FreeBSD_version >= 500005 struct task task; #endif struct timespec ctx_start; struct timespec lck_start; #if DRM_DMA_HISTOGRAM drm_histogram_t histo; #endif /* Callback to X server for context switch and for heavy-handed reset. */ char buf[DRM_BSZ]; /* Output buffer */ char *buf_rp; /* Read pointer */ char *buf_wp; /* Write pointer */ char *buf_end; /* End pointer */ struct sigio *buf_sigio; /* Processes waiting for SIGIO */ struct selinfo buf_sel; /* Workspace for select/poll */ int buf_readers; /* Processes waiting to read */ int buf_writers; /* Processes waiting to ctx switch */ int buf_selecting; /* True if poll sleeper */ /* Sysctl support */ struct drm_sysctl_info *sysctl; #ifdef DRM_AGP drm_agp_head_t *agp; #endif u_int32_t *ctx_bitmap; void *dev_private; } drm_device_t; /* Internal function definitions */ /* Misc. support (init.c) */ extern int drm_flags; extern void drm_parse_options(char *s); /* Device support (fops.c) */ extern drm_file_t *drm_find_file_by_proc(drm_device_t *dev, struct proc *p); extern int drm_open_helper(dev_t kdev, int flags, int fmt, struct proc *p, drm_device_t *dev); extern d_close_t drm_close; extern d_read_t drm_read; extern d_write_t drm_write; extern d_poll_t drm_poll; extern int drm_fsetown(dev_t kdev, u_long cmd, caddr_t data, int flags, struct proc *p); extern int drm_fgetown(dev_t kdev, u_long cmd, caddr_t data, int flags, struct proc *p); extern int drm_write_string(drm_device_t *dev, const char *s); #if 0 /* Mapping support (vm.c) */ extern unsigned long drm_vm_nopage(struct vm_area_struct *vma, unsigned long address, int write_access); extern unsigned long drm_vm_shm_nopage(struct vm_area_struct *vma, unsigned long address, int write_access); extern unsigned long drm_vm_dma_nopage(struct vm_area_struct *vma, unsigned long address, int write_access); extern void drm_vm_open(struct vm_area_struct *vma); extern void drm_vm_close(struct vm_area_struct *vma); extern int drm_mmap_dma(struct file *filp, struct vm_area_struct *vma); #endif extern d_mmap_t drm_mmap; /* Proc support (proc.c) */ extern int drm_sysctl_init(drm_device_t *dev); extern int drm_sysctl_cleanup(drm_device_t *dev); /* Memory management support (memory.c) */ extern void drm_mem_init(void); extern int drm_mem_info SYSCTL_HANDLER_ARGS; extern void *drm_alloc(size_t size, int area); extern void *drm_realloc(void *oldpt, size_t oldsize, size_t size, int area); extern char *drm_strdup(const char *s, int area); extern void drm_strfree(char *s, int area); extern void drm_free(void *pt, size_t size, int area); extern unsigned long drm_alloc_pages(int order, int area); extern void drm_free_pages(unsigned long address, int order, int area); extern void *drm_ioremap(unsigned long offset, unsigned long size); extern void drm_ioremapfree(void *pt, unsigned long size); #ifdef DRM_AGP extern void *drm_alloc_agp(int pages, u_int32_t type); extern int drm_free_agp(void *handle, int pages); extern int drm_bind_agp(void *handle, unsigned int start); extern int drm_unbind_agp(void *handle); #endif /* Buffer management support (bufs.c) */ extern int drm_order(unsigned long size); extern d_ioctl_t drm_addmap; extern d_ioctl_t drm_addbufs; extern d_ioctl_t drm_infobufs; extern d_ioctl_t drm_markbufs; extern d_ioctl_t drm_freebufs; extern d_ioctl_t drm_mapbufs; /* Buffer list management support (lists.c) */ extern int drm_waitlist_create(drm_waitlist_t *bl, int count); extern int drm_waitlist_destroy(drm_waitlist_t *bl); extern int drm_waitlist_put(drm_waitlist_t *bl, drm_buf_t *buf); extern drm_buf_t *drm_waitlist_get(drm_waitlist_t *bl); extern int drm_freelist_create(drm_freelist_t *bl, int count); extern int drm_freelist_destroy(drm_freelist_t *bl); extern int drm_freelist_put(drm_device_t *dev, drm_freelist_t *bl, drm_buf_t *buf); extern drm_buf_t *drm_freelist_get(drm_freelist_t *bl, int block); /* DMA support (gen_dma.c) */ extern void drm_dma_setup(drm_device_t *dev); extern void drm_dma_takedown(drm_device_t *dev); extern void drm_free_buffer(drm_device_t *dev, drm_buf_t *buf); extern void drm_reclaim_buffers(drm_device_t *dev, pid_t pid); extern int drm_context_switch(drm_device_t *dev, int old, int new); extern int drm_context_switch_complete(drm_device_t *dev, int new); extern void drm_wakeup(drm_device_t *dev, drm_buf_t *buf); extern void drm_clear_next_buffer(drm_device_t *dev); extern int drm_select_queue(drm_device_t *dev, void (*wrapper)(void *)); extern int drm_dma_enqueue(drm_device_t *dev, drm_dma_t *dma); extern int drm_dma_get_buffers(drm_device_t *dev, drm_dma_t *dma); #if DRM_DMA_HISTOGRAM extern int drm_histogram_slot(struct timespec *ts); extern void drm_histogram_compute(drm_device_t *dev, drm_buf_t *buf); #endif /* Misc. IOCTL support (ioctl.c) */ extern d_ioctl_t drm_irq_busid; extern d_ioctl_t drm_getunique; extern d_ioctl_t drm_setunique; /* Context IOCTL support (context.c) */ extern d_ioctl_t drm_resctx; extern d_ioctl_t drm_addctx; extern d_ioctl_t drm_modctx; extern d_ioctl_t drm_getctx; extern d_ioctl_t drm_switchctx; extern d_ioctl_t drm_newctx; extern d_ioctl_t drm_rmctx; /* Drawable IOCTL support (drawable.c) */ extern d_ioctl_t drm_adddraw; extern d_ioctl_t drm_rmdraw; /* Authentication IOCTL support (auth.c) */ extern int drm_add_magic(drm_device_t *dev, drm_file_t *priv, drm_magic_t magic); extern int drm_remove_magic(drm_device_t *dev, drm_magic_t magic); extern d_ioctl_t drm_getmagic; extern d_ioctl_t drm_authmagic; /* Locking IOCTL support (lock.c) */ extern d_ioctl_t drm_block; extern d_ioctl_t drm_unblock; extern int drm_lock_take(__volatile__ unsigned int *lock, unsigned int context); extern int drm_lock_transfer(drm_device_t *dev, __volatile__ unsigned int *lock, unsigned int context); extern int drm_lock_free(drm_device_t *dev, __volatile__ unsigned int *lock, unsigned int context); extern d_ioctl_t drm_finish; extern int drm_flush_unblock(drm_device_t *dev, int context, drm_lock_flags_t flags); extern int drm_flush_block_and_flush(drm_device_t *dev, int context, drm_lock_flags_t flags); /* Context Bitmap support (ctxbitmap.c) */ extern int drm_ctxbitmap_init(drm_device_t *dev); extern void drm_ctxbitmap_cleanup(drm_device_t *dev); extern int drm_ctxbitmap_next(drm_device_t *dev); extern void drm_ctxbitmap_free(drm_device_t *dev, int ctx_handle); #ifdef DRM_AGP /* AGP/GART support (agpsupport.c) */ extern drm_agp_head_t *drm_agp_init(void); extern d_ioctl_t drm_agp_acquire; extern d_ioctl_t drm_agp_release; extern d_ioctl_t drm_agp_enable; extern d_ioctl_t drm_agp_info; extern d_ioctl_t drm_agp_alloc; extern d_ioctl_t drm_agp_free; extern d_ioctl_t drm_agp_unbind; extern d_ioctl_t drm_agp_bind; #endif #endif #endif class="hl ppc">#else #define SL_ALLOC drmMalloc #define SL_FREE drmFree #define SL_RANDOM_DECL static void *state = NULL #define SL_RANDOM_INIT(seed) if (!state) state = drmRandomCreate(seed) #define SL_RANDOM drmRandom(state) #endif typedef struct SLEntry { unsigned long magic; /* SL_ENTRY_MAGIC */ unsigned long key; void *value; int levels; struct SLEntry *forward[1]; /* variable sized array */ } SLEntry, *SLEntryPtr; typedef struct SkipList { unsigned long magic; /* SL_LIST_MAGIC */ int level; int count; SLEntryPtr head; SLEntryPtr p0; /* Position for iteration */ } SkipList, *SkipListPtr; #if SL_MAIN extern void *drmSLCreate(void); extern int drmSLDestroy(void *l); extern int drmSLLookup(void *l, unsigned long key, void **value); extern int drmSLInsert(void *l, unsigned long key, void *value); extern int drmSLDelete(void *l, unsigned long key); extern int drmSLNext(void *l, unsigned long *key, void **value); extern int drmSLFirst(void *l, unsigned long *key, void **value); extern void drmSLDump(void *l); extern int drmSLLookupNeighbors(void *l, unsigned long key, unsigned long *prev_key, void **prev_value, unsigned long *next_key, void **next_value); #endif static SLEntryPtr SLCreateEntry(int max_level, unsigned long key, void *value) { SLEntryPtr entry; if (max_level < 0 || max_level > SL_MAX_LEVEL) max_level = SL_MAX_LEVEL; entry = SL_ALLOC(sizeof(*entry) + (max_level + 1) * sizeof(entry->forward[0])); if (!entry) return NULL; entry->magic = SL_ENTRY_MAGIC; entry->key = key; entry->value = value; entry->levels = max_level + 1; return entry; } static int SLRandomLevel(void) { int level = 1; SL_RANDOM_DECL; SL_RANDOM_INIT(SL_RANDOM_SEED); while ((SL_RANDOM & 0x01) && level < SL_MAX_LEVEL) ++level; return level; } void *drmSLCreate(void) { SkipListPtr list; int i; list = SL_ALLOC(sizeof(*list)); if (!list) return NULL; list->magic = SL_LIST_MAGIC; list->level = 0; list->head = SLCreateEntry(SL_MAX_LEVEL, 0, NULL); list->count = 0; for (i = 0; i <= SL_MAX_LEVEL; i++) list->head->forward[i] = NULL; return list; } int drmSLDestroy(void *l) { SkipListPtr list = (SkipListPtr)l; SLEntryPtr entry; SLEntryPtr next; if (list->magic != SL_LIST_MAGIC) return -1; /* Bad magic */ for (entry = list->head; entry; entry = next) { if (entry->magic != SL_ENTRY_MAGIC) return -1; /* Bad magic */ next = entry->forward[0]; entry->magic = SL_FREED_MAGIC; SL_FREE(entry); } list->magic = SL_FREED_MAGIC; SL_FREE(list); return 0; } static SLEntryPtr SLLocate(void *l, unsigned long key, SLEntryPtr *update) { SkipListPtr list = (SkipListPtr)l; SLEntryPtr entry; int i; if (list->magic != SL_LIST_MAGIC) return NULL; for (i = list->level, entry = list->head; i >= 0; i--) { while (entry->forward[i] && entry->forward[i]->key < key) entry = entry->forward[i]; update[i] = entry; } return entry->forward[0]; } int drmSLInsert(void *l, unsigned long key, void *value) { SkipListPtr list = (SkipListPtr)l; SLEntryPtr entry; SLEntryPtr update[SL_MAX_LEVEL + 1]; int level; int i; if (list->magic != SL_LIST_MAGIC) return -1; /* Bad magic */ entry = SLLocate(list, key, update); if (entry && entry->key == key) return 1; /* Already in list */ level = SLRandomLevel(); if (level > list->level) { level = ++list->level; update[level] = list->head; } entry = SLCreateEntry(level, key, value); /* Fix up forward pointers */ for (i = 0; i <= level; i++) { entry->forward[i] = update[i]->forward[i]; update[i]->forward[i] = entry; } ++list->count; return 0; /* Added to table */ } int drmSLDelete(void *l, unsigned long key) { SkipListPtr list = (SkipListPtr)l; SLEntryPtr update[SL_MAX_LEVEL + 1]; SLEntryPtr entry; int i; if (list->magic != SL_LIST_MAGIC) return -1; /* Bad magic */ entry = SLLocate(list, key, update); if (!entry || entry->key != key) return 1; /* Not found */ /* Fix up forward pointers */ for (i = 0; i <= list->level; i++) { if (update[i]->forward[i] == entry) update[i]->forward[i] = entry->forward[i]; } entry->magic = SL_FREED_MAGIC; SL_FREE(entry); while (list->level && !list->head->forward[list->level]) --list->level; --list->count; return 0; } int drmSLLookup(void *l, unsigned long key, void **value) { SkipListPtr list = (SkipListPtr)l; SLEntryPtr update[SL_MAX_LEVEL + 1]; SLEntryPtr entry; entry = SLLocate(list, key, update); if (entry && entry->key == key) { *value = entry; return 0; } *value = NULL; return -1; } int drmSLLookupNeighbors(void *l, unsigned long key, unsigned long *prev_key, void **prev_value, unsigned long *next_key, void **next_value) { SkipListPtr list = (SkipListPtr)l; SLEntryPtr update[SL_MAX_LEVEL + 1]; SLEntryPtr entry; int retcode = 0; entry = SLLocate(list, key, update); *prev_key = *next_key = key; *prev_value = *next_value = NULL; if (update[0]) { *prev_key = update[0]->key; *prev_value = update[0]->value; ++retcode; if (update[0]->forward[0]) { *next_key = update[0]->forward[0]->key; *next_value = update[0]->forward[0]->value; ++retcode; } } return retcode; } int drmSLNext(void *l, unsigned long *key, void **value) { SkipListPtr list = (SkipListPtr)l; SLEntryPtr entry; if (list->magic != SL_LIST_MAGIC) return -1; /* Bad magic */ entry = list->p0; if (entry) { list->p0 = entry->forward[0]; *key = entry->key; *value = entry->value; return 1; } list->p0 = NULL; return 0; } int drmSLFirst(void *l, unsigned long *key, void **value) { SkipListPtr list = (SkipListPtr)l; if (list->magic != SL_LIST_MAGIC) return -1; /* Bad magic */ list->p0 = list->head->forward[0]; return drmSLNext(list, key, value); } /* Dump internal data structures for debugging. */ void drmSLDump(void *l) { SkipListPtr list = (SkipListPtr)l; SLEntryPtr entry; int i; if (list->magic != SL_LIST_MAGIC) { printf("Bad magic: 0x%08lx (expected 0x%08lx)\n", list->magic, SL_LIST_MAGIC); return; } printf("Level = %d, count = %d\n", list->level, list->count); for (entry = list->head; entry; entry = entry->forward[0]) { if (entry->magic != SL_ENTRY_MAGIC) { printf("Bad magic: 0x%08lx (expected 0x%08lx)\n", list->magic, SL_ENTRY_MAGIC); } printf("\nEntry %p <0x%08lx, %p> has %2d levels\n", entry, entry->key, entry->value, entry->levels); for (i = 0; i < entry->levels; i++) { if (entry->forward[i]) { printf(" %2d: %p <0x%08lx, %p>\n", i, entry->forward[i], entry->forward[i]->key, entry->forward[i]->value); } else { printf(" %2d: %p\n", i, entry->forward[i]); } } } } #if SL_MAIN static void print(SkipListPtr list) { unsigned long key; void *value; if (drmSLFirst(list, &key, &value)) { do { printf("key = %5lu, value = %p\n", key, value); } while (drmSLNext(list, &key, &value)); } } static double do_time(int size, int iter) { SkipListPtr list; int i, j; unsigned long keys[1000000]; unsigned long previous; unsigned long key; void *value; struct timeval start, stop; double usec; SL_RANDOM_DECL; SL_RANDOM_INIT(12345); list = drmSLCreate(); for (i = 0; i < size; i++) { keys[i] = SL_RANDOM; drmSLInsert(list, keys[i], NULL); } previous = 0; if (drmSLFirst(list, &key, &value)) { do { if (key <= previous) { printf( "%lu !< %lu\n", previous, key); } previous = key; } while (drmSLNext(list, &key, &value)); } gettimeofday(&start, NULL); for (j = 0; j < iter; j++) { for (i = 0; i < size; i++) { if (drmSLLookup(list, keys[i], &value)) printf("Error %lu %d\n", keys[i], i); } } gettimeofday(&stop, NULL); usec = (double)(stop.tv_sec * 1000000 + stop.tv_usec - start.tv_sec * 1000000 - start.tv_usec) / (size * iter); printf("%0.2f microseconds for list length %d\n", usec, size); drmSLDestroy(list); return usec; } static void print_neighbors(void *list, unsigned long key) { unsigned long prev_key = 0; unsigned long next_key = 0; void *prev_value; void *next_value; int retval; retval = drmSLLookupNeighbors(list, key, &prev_key, &prev_value, &next_key, &next_value); printf("Neighbors of %5lu: %d %5lu %5lu\n", key, retval, prev_key, next_key); } int main(void) { SkipListPtr list; double usec, usec2, usec3, usec4; list = drmSLCreate(); printf( "list at %p\n", list); print(list); printf("\n==============================\n\n"); drmSLInsert(list, 123, NULL); drmSLInsert(list, 213, NULL); drmSLInsert(list, 50, NULL); print(list); printf("\n==============================\n\n"); print_neighbors(list, 0); print_neighbors(list, 50); print_neighbors(list, 51); print_neighbors(list, 123); print_neighbors(list, 200); print_neighbors(list, 213); print_neighbors(list, 256); printf("\n==============================\n\n"); drmSLDelete(list, 50); print(list); printf("\n==============================\n\n"); drmSLDump(list); drmSLDestroy(list); printf("\n==============================\n\n"); usec = do_time(100, 10000); usec2 = do_time(1000, 500); printf("Table size increased by %0.2f, search time increased by %0.2f\n", 1000.0/100.0, usec2 / usec); usec3 = do_time(10000, 50); printf("Table size increased by %0.2f, search time increased by %0.2f\n",