1/*
2 * Copyright © 2003 Anders Carlsson
3 *
4 * Permission to use, copy, modify, distribute, and sell this software and its
5 * documentation for any purpose is hereby granted without fee, provided that
6 * the above copyright notice appear in all copies and that both that
7 * copyright notice and this permission notice appear in supporting
8 * documentation, and that the name of Anders Carlsson not be used in
9 * advertising or publicity pertaining to distribution of the software without
10 * specific, written prior permission.  Anders Carlsson makes no
11 * representations about the suitability of this software for any purpose.  It
12 * is provided "as is" without express or implied warranty.
13 *
14 * ANDERS CARLSSON DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
15 * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
16 * EVENT SHALL ANDERS CARLSSON BE LIABLE FOR ANY SPECIAL, INDIRECT OR
17 * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
18 * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
19 * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
20 * PERFORMANCE OF THIS SOFTWARE.
21 */
22
23/** @file
24 * This allocator allocates blocks of memory by maintaining a list of areas.
25 * When allocating, the contiguous block of areas with the minimum eviction
26 * cost is found and evicted in order to make room for the new allocation.
27 */
28
29#include "exa_priv.h"
30
31#include <limits.h>
32#include <assert.h>
33#include <stdlib.h>
34
35#if DEBUG_OFFSCREEN
36#define DBG_OFFSCREEN(a) ErrorF a
37#else
38#define DBG_OFFSCREEN(a)
39#endif
40
41#if DEBUG_OFFSCREEN
42static void
43ExaOffscreenValidate (ScreenPtr pScreen)
44{
45    ExaScreenPriv (pScreen);
46    ExaOffscreenArea *prev = 0, *area;
47
48    assert (pExaScr->info->offScreenAreas->base_offset ==
49	    pExaScr->info->offScreenBase);
50    for (area = pExaScr->info->offScreenAreas; area; area = area->next)
51    {
52	assert (area->offset >= area->base_offset &&
53		area->offset < (area->base_offset + area->size));
54	if (prev)
55	    assert (prev->base_offset + prev->size == area->base_offset);
56	prev = area;
57    }
58    assert (prev->base_offset + prev->size == pExaScr->info->memorySize);
59}
60#else
61#define ExaOffscreenValidate(s)
62#endif
63
64static ExaOffscreenArea *
65ExaOffscreenKickOut (ScreenPtr pScreen, ExaOffscreenArea *area)
66{
67    if (area->save)
68	(*area->save) (pScreen, area);
69    return exaOffscreenFree (pScreen, area);
70}
71
72static void
73exaUpdateEvictionCost(ExaOffscreenArea *area, unsigned offScreenCounter)
74{
75    unsigned age;
76
77    if (area->state == ExaOffscreenAvail)
78	return;
79
80    age = offScreenCounter - area->last_use;
81
82    /* This is unlikely to happen, but could result in a division by zero... */
83    if (age > (UINT_MAX / 2)) {
84	age = UINT_MAX / 2;
85	area->last_use = offScreenCounter - age;
86    }
87
88    area->eviction_cost = area->size / age;
89}
90
91static ExaOffscreenArea *
92exaFindAreaToEvict(ExaScreenPrivPtr pExaScr, int size, int align)
93{
94    ExaOffscreenArea *begin, *end, *best;
95    unsigned cost, best_cost;
96    int avail, real_size;
97
98    best_cost = UINT_MAX;
99    begin = end = pExaScr->info->offScreenAreas;
100    avail = 0;
101    cost = 0;
102    best = 0;
103
104    while (end != NULL)
105    {
106	restart:
107	while (begin != NULL && begin->state == ExaOffscreenLocked)
108	    begin = end = begin->next;
109
110	if (begin == NULL)
111	    break;
112
113	/* adjust size needed to account for alignment loss for this area */
114	real_size = size + (begin->base_offset + begin->size - size) % align;
115
116	while (avail < real_size && end != NULL)
117	{
118	    if (end->state == ExaOffscreenLocked) {
119		/* Can't more room here, restart after this locked area */
120		avail = 0;
121		cost = 0;
122		begin = end;
123		goto restart;
124	    }
125	    avail += end->size;
126	    exaUpdateEvictionCost(end, pExaScr->offScreenCounter);
127	    cost += end->eviction_cost;
128	    end = end->next;
129	}
130
131	/* Check the cost, update best */
132	if (avail >= real_size && cost < best_cost) {
133	    best = begin;
134	    best_cost = cost;
135	}
136
137	avail -= begin->size;
138	cost -= begin->eviction_cost;
139	begin = begin->next;
140    }
141
142    return best;
143}
144
145/**
146 * exaOffscreenAlloc allocates offscreen memory
147 *
148 * @param pScreen current screen
149 * @param size size in bytes of the allocation
150 * @param align byte alignment requirement for the offset of the allocated area
151 * @param locked whether the allocated area is locked and can't be kicked out
152 * @param save callback for when the area is evicted from memory
153 * @param privdata private data for the save callback.
154 *
155 * Allocates offscreen memory from the device associated with pScreen.  size
156 * and align deteremine where and how large the allocated area is, and locked
157 * will mark whether it should be held in card memory.  privdata may be any
158 * pointer for the save callback when the area is removed.
159 *
160 * Note that locked areas do get evicted on VT switch unless the driver
161 * requested version 2.1 or newer behavior.  In that case, the save callback is
162 * still called.
163 */
164ExaOffscreenArea *
165exaOffscreenAlloc (ScreenPtr pScreen, int size, int align,
166                   Bool locked,
167                   ExaOffscreenSaveProc save,
168                   pointer privData)
169{
170    ExaOffscreenArea *area;
171    ExaScreenPriv (pScreen);
172    int real_size = 0, largest_avail = 0;
173#if DEBUG_OFFSCREEN
174    static int number = 0;
175    ErrorF("================= ============ allocating a new pixmap %d\n", ++number);
176#endif
177
178    ExaOffscreenValidate (pScreen);
179    if (!align)
180	align = 1;
181
182    if (!size)
183    {
184	DBG_OFFSCREEN (("Alloc 0x%x -> EMPTY\n", size));
185	return NULL;
186    }
187
188    /* throw out requests that cannot fit */
189    if (size > (pExaScr->info->memorySize - pExaScr->info->offScreenBase))
190    {
191	DBG_OFFSCREEN (("Alloc 0x%x vs (0x%lx) -> TOBIG\n", size,
192			pExaScr->info->memorySize -
193			pExaScr->info->offScreenBase));
194	return NULL;
195    }
196
197    /* Try to find a free space that'll fit. */
198    for (area = pExaScr->info->offScreenAreas; area; area = area->next)
199    {
200	/* skip allocated areas */
201	if (area->state != ExaOffscreenAvail)
202	    continue;
203
204	/* adjust size to match alignment requirement */
205	real_size = size + (area->base_offset + area->size - size) % align;
206
207	/* does it fit? */
208	if (real_size <= area->size)
209	    break;
210
211	if (area->size > largest_avail)
212	    largest_avail = area->size;
213    }
214
215    if (!area)
216    {
217	area = exaFindAreaToEvict(pExaScr, size, align);
218
219	if (!area)
220	{
221	    DBG_OFFSCREEN (("Alloc 0x%x -> NOSPACE\n", size));
222	    /* Could not allocate memory */
223	    ExaOffscreenValidate (pScreen);
224	    return NULL;
225	}
226
227	/* adjust size needed to account for alignment loss for this area */
228	real_size = size + (area->base_offset + area->size - size) % align;
229
230	/*
231	 * Kick out first area if in use
232	 */
233	if (area->state != ExaOffscreenAvail)
234	    area = ExaOffscreenKickOut (pScreen, area);
235	/*
236	 * Now get the system to merge the other needed areas together
237	 */
238	while (area->size < real_size)
239	{
240	    assert (area->next && area->next->state == ExaOffscreenRemovable);
241	    (void) ExaOffscreenKickOut (pScreen, area->next);
242	}
243    }
244
245    /* save extra space in new area */
246    if (real_size < area->size)
247    {
248	ExaOffscreenArea   *new_area = malloc(sizeof (ExaOffscreenArea));
249	if (!new_area)
250	    return NULL;
251	new_area->base_offset = area->base_offset;
252
253	new_area->offset = new_area->base_offset;
254	new_area->align = 0;
255	new_area->size = area->size - real_size;
256	new_area->state = ExaOffscreenAvail;
257	new_area->save = NULL;
258	new_area->last_use = 0;
259	new_area->eviction_cost = 0;
260	new_area->next = area;
261	new_area->prev = area->prev;
262	if (area->prev->next)
263	    area->prev->next = new_area;
264	else
265	    pExaScr->info->offScreenAreas = new_area;
266	area->prev = new_area;
267	area->base_offset = new_area->base_offset + new_area->size;
268	area->size = real_size;
269    } else
270	pExaScr->numOffscreenAvailable--;
271
272    /*
273     * Mark this area as in use
274     */
275    if (locked)
276	area->state = ExaOffscreenLocked;
277    else
278	area->state = ExaOffscreenRemovable;
279    area->privData = privData;
280    area->save = save;
281    area->last_use = pExaScr->offScreenCounter++;
282    area->offset = (area->base_offset + align - 1);
283    area->offset -= area->offset % align;
284    area->align = align;
285
286    ExaOffscreenValidate (pScreen);
287
288    DBG_OFFSCREEN (("Alloc 0x%x -> 0x%x (0x%x)\n", size,
289		    area->base_offset, area->offset));
290    return area;
291}
292
293/**
294 * Ejects all offscreen areas, and uninitializes the offscreen memory manager.
295 */
296void
297ExaOffscreenSwapOut (ScreenPtr pScreen)
298{
299    ExaScreenPriv (pScreen);
300
301    ExaOffscreenValidate (pScreen);
302    /* loop until a single free area spans the space */
303    for (;;)
304    {
305	ExaOffscreenArea *area = pExaScr->info->offScreenAreas;
306
307	if (!area)
308	    break;
309	if (area->state == ExaOffscreenAvail)
310	{
311	    area = area->next;
312	    if (!area)
313		break;
314	}
315	assert (area->state != ExaOffscreenAvail);
316	(void) ExaOffscreenKickOut (pScreen, area);
317	ExaOffscreenValidate (pScreen);
318    }
319    ExaOffscreenValidate (pScreen);
320    ExaOffscreenFini (pScreen);
321}
322
323/** Ejects all pixmaps managed by EXA. */
324static void
325ExaOffscreenEjectPixmaps (ScreenPtr pScreen)
326{
327    ExaScreenPriv (pScreen);
328
329    ExaOffscreenValidate (pScreen);
330    /* loop until a single free area spans the space */
331    for (;;)
332    {
333	ExaOffscreenArea *area;
334
335	for (area = pExaScr->info->offScreenAreas; area != NULL;
336	     area = area->next)
337	{
338	    if (area->state == ExaOffscreenRemovable &&
339		area->save == exaPixmapSave)
340	    {
341		(void) ExaOffscreenKickOut (pScreen, area);
342		ExaOffscreenValidate (pScreen);
343		break;
344	    }
345	}
346	if (area == NULL)
347	    break;
348    }
349    ExaOffscreenValidate (pScreen);
350}
351
352void
353ExaOffscreenSwapIn (ScreenPtr pScreen)
354{
355    exaOffscreenInit (pScreen);
356}
357
358/**
359 * Prepares EXA for disabling of FB access, or restoring it.
360 *
361 * In version 2.1, the disabling results in pixmaps being ejected, while other
362 * allocations remain.  With this plus the prevention of migration while
363 * swappedOut is set, EXA by itself should not cause any access of the
364 * framebuffer to occur while swapped out.  Any remaining issues are the
365 * responsibility of the driver.
366 *
367 * Prior to version 2.1, all allocations, including locked ones, are ejected
368 * when access is disabled, and the allocator is torn down while swappedOut
369 * is set.  This is more drastic, and caused implementation difficulties for
370 * many drivers that could otherwise handle the lack of FB access while
371 * swapped out.
372 */
373void
374exaEnableDisableFBAccess (int index, Bool enable)
375{
376    ScreenPtr pScreen = screenInfo.screens[index];
377    ExaScreenPriv (pScreen);
378
379    if (pExaScr->info->flags & EXA_HANDLES_PIXMAPS)
380	return;
381
382    if (!enable && pExaScr->disableFbCount++ == 0) {
383	if (pExaScr->info->exa_minor < 1)
384	    ExaOffscreenSwapOut (pScreen);
385	else
386	    ExaOffscreenEjectPixmaps (pScreen);
387	pExaScr->swappedOut = TRUE;
388    }
389
390    if (enable && --pExaScr->disableFbCount == 0) {
391	if (pExaScr->info->exa_minor < 1)
392	    ExaOffscreenSwapIn (pScreen);
393	pExaScr->swappedOut = FALSE;
394    }
395}
396
397/* merge the next free area into this one */
398static void
399ExaOffscreenMerge (ExaScreenPrivPtr pExaScr, ExaOffscreenArea *area)
400{
401    ExaOffscreenArea	*next = area->next;
402
403    /* account for space */
404    area->size += next->size;
405    /* frob pointer */
406    area->next = next->next;
407    if (area->next)
408	area->next->prev = area;
409    else
410	pExaScr->info->offScreenAreas->prev = area;
411    free(next);
412
413    pExaScr->numOffscreenAvailable--;
414}
415
416/**
417 * exaOffscreenFree frees an allocation.
418 *
419 * @param pScreen current screen
420 * @param area offscreen area to free
421 *
422 * exaOffscreenFree frees an allocation created by exaOffscreenAlloc.  Note that
423 * the save callback of the area is not called, and it is up to the driver to
424 * do any cleanup necessary as a result.
425 *
426 * @return pointer to the newly freed area. This behavior should not be relied
427 * on.
428 */
429ExaOffscreenArea *
430exaOffscreenFree (ScreenPtr pScreen, ExaOffscreenArea *area)
431{
432    ExaScreenPriv(pScreen);
433    ExaOffscreenArea	*next = area->next;
434    ExaOffscreenArea	*prev;
435
436    DBG_OFFSCREEN (("Free 0x%x -> 0x%x (0x%x)\n", area->size,
437		    area->base_offset, area->offset));
438    ExaOffscreenValidate (pScreen);
439
440    area->state = ExaOffscreenAvail;
441    area->save = NULL;
442    area->last_use = 0;
443    area->eviction_cost = 0;
444    /*
445     * Find previous area
446     */
447    if (area == pExaScr->info->offScreenAreas)
448	prev = NULL;
449    else
450	prev = area->prev;
451
452    pExaScr->numOffscreenAvailable++;
453
454    /* link with next area if free */
455    if (next && next->state == ExaOffscreenAvail)
456	ExaOffscreenMerge (pExaScr, area);
457
458    /* link with prev area if free */
459    if (prev && prev->state == ExaOffscreenAvail)
460    {
461	area = prev;
462	ExaOffscreenMerge (pExaScr, area);
463    }
464
465    ExaOffscreenValidate (pScreen);
466    DBG_OFFSCREEN(("\tdone freeing\n"));
467    return area;
468}
469
470void
471ExaOffscreenMarkUsed (PixmapPtr pPixmap)
472{
473    ExaPixmapPriv (pPixmap);
474    ExaScreenPriv (pPixmap->drawable.pScreen);
475
476    if (!pExaPixmap || !pExaPixmap->area)
477	return;
478
479    pExaPixmap->area->last_use = pExaScr->offScreenCounter++;
480}
481
482/**
483 * Defragment offscreen memory by compacting allocated areas at the end of it,
484 * leaving the total amount of memory available as a single area at the
485 * beginning (when there are no pinned allocations).
486 */
487_X_HIDDEN ExaOffscreenArea*
488ExaOffscreenDefragment (ScreenPtr pScreen)
489{
490    ExaScreenPriv (pScreen);
491    ExaOffscreenArea *area, *largest_available = NULL;
492    int largest_size = 0;
493    PixmapPtr pDstPix;
494    ExaPixmapPrivPtr pExaDstPix;
495
496    pDstPix = (*pScreen->CreatePixmap) (pScreen, 0, 0, 0, 0);
497
498    if (!pDstPix)
499	return NULL;
500
501    pExaDstPix = ExaGetPixmapPriv (pDstPix);
502    pExaDstPix->use_gpu_copy = TRUE;
503
504    for (area = pExaScr->info->offScreenAreas->prev;
505	 area != pExaScr->info->offScreenAreas;
506	 )
507    {
508	ExaOffscreenArea *prev = area->prev;
509	PixmapPtr pSrcPix;
510	ExaPixmapPrivPtr pExaSrcPix;
511	Bool save_use_gpu_copy;
512	int save_pitch;
513
514	if (area->state != ExaOffscreenAvail ||
515	    prev->state == ExaOffscreenLocked ||
516	    (prev->state == ExaOffscreenRemovable &&
517	     prev->save != exaPixmapSave)) {
518	    area = prev;
519	    continue;
520	}
521
522	if (prev->state == ExaOffscreenAvail) {
523	    if (area == largest_available) {
524		largest_available = prev;
525		largest_size += prev->size;
526	    }
527	    area = prev;
528	    ExaOffscreenMerge (pExaScr, area);
529	    continue;
530	}
531
532	if (area->size > largest_size) {
533	    largest_available = area;
534	    largest_size = area->size;
535	}
536
537	pSrcPix = prev->privData;
538	pExaSrcPix = ExaGetPixmapPriv (pSrcPix);
539
540	pExaDstPix->fb_ptr = pExaScr->info->memoryBase +
541	    area->base_offset + area->size - prev->size + prev->base_offset -
542	    prev->offset;
543	pExaDstPix->fb_ptr -= (unsigned long)pExaDstPix->fb_ptr % prev->align;
544
545	if (pExaDstPix->fb_ptr <= pExaSrcPix->fb_ptr) {
546	    area = prev;
547	    continue;
548	}
549
550	if (!(pExaScr->info->flags & EXA_SUPPORTS_OFFSCREEN_OVERLAPS) &&
551	    (pExaSrcPix->fb_ptr + prev->size) > pExaDstPix->fb_ptr) {
552	    area = prev;
553	    continue;
554	}
555
556	save_use_gpu_copy = pExaSrcPix->use_gpu_copy;
557	save_pitch = pSrcPix->devKind;
558
559	pExaSrcPix->use_gpu_copy = TRUE;
560	pSrcPix->devKind = pExaSrcPix->fb_pitch;
561
562	pDstPix->drawable.width = pSrcPix->drawable.width;
563	pDstPix->devKind = pSrcPix->devKind;
564	pDstPix->drawable.height = pSrcPix->drawable.height;
565	pDstPix->drawable.depth = pSrcPix->drawable.depth;
566	pDstPix->drawable.bitsPerPixel = pSrcPix->drawable.bitsPerPixel;
567
568	if (!pExaScr->info->PrepareCopy (pSrcPix, pDstPix, -1, -1, GXcopy, ~0)) {
569	    pExaSrcPix->use_gpu_copy = save_use_gpu_copy;
570	    pSrcPix->devKind = save_pitch;
571	    area = prev;
572	    continue;
573	}
574
575	pExaScr->info->Copy (pDstPix, 0, 0, 0, 0, pDstPix->drawable.width,
576			     pDstPix->drawable.height);
577	pExaScr->info->DoneCopy (pDstPix);
578	exaMarkSync (pScreen);
579
580	DBG_OFFSCREEN(("Before swap: prev=0x%08x-0x%08x-0x%08x area=0x%08x-0x%08x-0x%08x\n",
581		       prev->base_offset, prev->offset, prev->base_offset + prev->size,
582		       area->base_offset, area->offset, area->base_offset + area->size));
583
584	/* Calculate swapped area offsets and sizes */
585	area->base_offset = prev->base_offset;
586	area->offset = area->base_offset;
587	prev->offset += pExaDstPix->fb_ptr - pExaSrcPix->fb_ptr;
588	assert(prev->offset >= pExaScr->info->offScreenBase &&
589	       prev->offset < pExaScr->info->memorySize);
590	prev->base_offset = prev->offset;
591	if (area->next)
592	    prev->size = area->next->base_offset - prev->base_offset;
593	else
594	    prev->size = pExaScr->info->memorySize - prev->base_offset;
595	area->size = prev->base_offset - area->base_offset;
596
597	DBG_OFFSCREEN(("After swap: area=0x%08x-0x%08x-0x%08x prev=0x%08x-0x%08x-0x%08x\n",
598		       area->base_offset, area->offset, area->base_offset + area->size,
599		       prev->base_offset, prev->offset, prev->base_offset + prev->size));
600
601	/* Swap areas in list */
602	if (area->next)
603	    area->next->prev = prev;
604	else
605	    pExaScr->info->offScreenAreas->prev = prev;
606	if (prev->prev->next)
607	    prev->prev->next = area;
608	else
609	    pExaScr->info->offScreenAreas = area;
610	prev->next = area->next;
611	area->next = prev;
612	area->prev = prev->prev;
613	prev->prev = area;
614	if (!area->prev->next)
615	    pExaScr->info->offScreenAreas = area;
616
617#if DEBUG_OFFSCREEN
618	if (prev->prev == prev || prev->next == prev)
619	    ErrorF("Whoops, prev points to itself!\n");
620
621	if (area->prev == area || area->next == area)
622	    ErrorF("Whoops, area points to itself!\n");
623#endif
624
625	pExaSrcPix->fb_ptr = pExaDstPix->fb_ptr;
626	pExaSrcPix->use_gpu_copy = save_use_gpu_copy;
627	pSrcPix->devKind = save_pitch;
628    }
629
630    pDstPix->drawable.width = 0;
631    pDstPix->drawable.height = 0;
632    pDstPix->drawable.depth = 0;
633    pDstPix->drawable.bitsPerPixel = 0;
634
635    (*pScreen->DestroyPixmap) (pDstPix);
636
637    if (area->state == ExaOffscreenAvail && area->size > largest_size)
638	return area;
639
640    return largest_available;
641}
642
643/**
644 * exaOffscreenInit initializes the offscreen memory manager.
645 *
646 * @param pScreen current screen
647 *
648 * exaOffscreenInit is called by exaDriverInit to set up the memory manager for
649 * the screen, if any offscreen memory is available.
650 */
651Bool
652exaOffscreenInit (ScreenPtr pScreen)
653{
654    ExaScreenPriv (pScreen);
655    ExaOffscreenArea *area;
656
657    /* Allocate a big free area */
658    area = malloc(sizeof (ExaOffscreenArea));
659
660    if (!area)
661	return FALSE;
662
663    area->state = ExaOffscreenAvail;
664    area->base_offset = pExaScr->info->offScreenBase;
665    area->offset = area->base_offset;
666    area->align = 0;
667    area->size = pExaScr->info->memorySize - area->base_offset;
668    area->save = NULL;
669    area->next = NULL;
670    area->prev = area;
671    area->last_use = 0;
672    area->eviction_cost = 0;
673
674    /* Add it to the free areas */
675    pExaScr->info->offScreenAreas = area;
676    pExaScr->offScreenCounter = 1;
677    pExaScr->numOffscreenAvailable = 1;
678
679    ExaOffscreenValidate (pScreen);
680
681    return TRUE;
682}
683
684void
685ExaOffscreenFini (ScreenPtr pScreen)
686{
687    ExaScreenPriv (pScreen);
688    ExaOffscreenArea *area;
689
690    /* just free all of the area records */
691    while ((area = pExaScr->info->offScreenAreas))
692    {
693	pExaScr->info->offScreenAreas = area->next;
694	free(area);
695    }
696}
697