1/*
2 * Copyright 2008-2011, Ingo Weinhold, ingo_weinhold@gmx.de.
3 * Distributed under the terms of the MIT License.
4 */
5
6
7/*!	Implementation of a physical page mapping strategy (PhysicalPageMapper,
8	TranslationMapPhysicalPageMapper) suitable for machines with a lot of
9	memory, i.e. more than we can afford to completely map into the kernel
10	address space.
11
12	We allocate a single page table (one page) that can map 1024 pages and
13	a corresponding virtual address space region (4 MB). Each of those 1024
14	slots can map a physical page. We reserve a fixed amount of slots per CPU.
15	They will be used for physical operations on that CPU (memset()/memcpy()
16	and {get,put}_physical_page_current_cpu()). A few slots we reserve for each
17	translation map (TranslationMapPhysicalPageMapper). Those will only be used
18	with the translation map locked, mapping a page table page. The remaining
19	slots remain in the global pool and are given out by get_physical_page().
20
21	When we run out of slots, we allocate another page table (and virtual
22	address space region).
23*/
24
25
26#include "paging/x86_physical_page_mapper_large_memory.h"
27
28#include <new>
29
30#include <AutoDeleter.h>
31
32#include <cpu.h>
33#include <lock.h>
34#include <smp.h>
35#include <util/AutoLock.h>
36#include <util/ThreadAutoLock.h>
37#include <vm/vm.h>
38#include <vm/vm_types.h>
39#include <vm/VMAddressSpace.h>
40
41#include "paging/x86_physical_page_mapper.h"
42#include "paging/X86PagingStructures.h"
43#include "paging/X86VMTranslationMap.h"
44
45
46// The number of slots we reserve per translation map from mapping page tables.
47// One slot would suffice, since the map is locked while mapping a page table,
48// but we re-use several slots on a LRU-basis so that we can keep the mappings
49// a little longer, thus avoiding re-mapping.
50#define SLOTS_PER_TRANSLATION_MAP		4
51
52
53using X86LargePhysicalPageMapper::PhysicalPageSlot;
54using X86LargePhysicalPageMapper::PhysicalPageSlotPool;
55
56
57class PhysicalPageSlotQueue {
58public:
59								PhysicalPageSlotQueue();
60
61	inline	PhysicalPageSlot*	GetSlot();
62	inline	void				GetSlots(PhysicalPageSlot*& slot1,
63									PhysicalPageSlot*& slot2);
64	inline	void				PutSlot(PhysicalPageSlot* slot);
65	inline	void				PutSlots(PhysicalPageSlot* slot1,
66									PhysicalPageSlot* slot2);
67
68private:
69			PhysicalPageSlot*	fSlots;
70			ConditionVariable	fFreeSlotCondition;
71			ConditionVariable	fFreeSlotsCondition;
72};
73
74
75struct PhysicalPageOpsCPUData {
76	PhysicalPageSlotQueue	user;
77		// Used when copying from/to user memory. This can cause a page fault
78		// which might need to memcpy()/memset() a page when being handled.
79	PhysicalPageSlotQueue	kernel;
80		// Used when memset()ing or when memcpy()ing memory non-user memory.
81	PhysicalPageSlot*		interruptSlot;
82
83			void				Init();
84
85private:
86	static	PhysicalPageSlot*	_GetInitialSlot();
87};
88
89
90// #pragma mark -
91
92
93class LargeMemoryTranslationMapPhysicalPageMapper
94	: public TranslationMapPhysicalPageMapper {
95public:
96								LargeMemoryTranslationMapPhysicalPageMapper();
97	virtual						~LargeMemoryTranslationMapPhysicalPageMapper();
98
99			status_t			Init();
100
101	virtual	void				Delete();
102
103	virtual	void*				GetPageTableAt(phys_addr_t physicalAddress);
104
105private:
106			struct page_slot {
107				PhysicalPageSlot*	slot;
108				phys_addr_t			physicalAddress;
109				CPUSet				valid;
110			};
111
112			page_slot			fSlots[SLOTS_PER_TRANSLATION_MAP];
113			int32				fSlotCount;	// must be a power of 2
114			int32				fNextSlot;
115};
116
117
118class LargeMemoryPhysicalPageMapper : public X86PhysicalPageMapper {
119public:
120								LargeMemoryPhysicalPageMapper();
121
122			status_t			Init(kernel_args* args,
123									PhysicalPageSlotPool* initialPools,
124									int32 initalPoolCount, size_t poolSize,
125									TranslationMapPhysicalPageMapper*&
126										_kernelPageMapper);
127
128	virtual	status_t			CreateTranslationMapPhysicalPageMapper(
129									TranslationMapPhysicalPageMapper** _mapper);
130
131	virtual	void*				InterruptGetPageTableAt(
132									phys_addr_t physicalAddress);
133
134	virtual	status_t			GetPage(phys_addr_t physicalAddress,
135									addr_t* virtualAddress, void** handle);
136	virtual	status_t			PutPage(addr_t virtualAddress, void* handle);
137
138	virtual	status_t			GetPageCurrentCPU(phys_addr_t physicalAddress,
139									addr_t* virtualAddress, void** handle);
140	virtual	status_t			PutPageCurrentCPU(addr_t virtualAddress,
141									void* handle);
142
143	virtual	status_t			GetPageDebug(phys_addr_t physicalAddress,
144									addr_t* virtualAddress, void** handle);
145	virtual	status_t			PutPageDebug(addr_t virtualAddress,
146									void* handle);
147
148	virtual	status_t			MemsetPhysical(phys_addr_t address, int value,
149									phys_size_t length);
150	virtual	status_t			MemcpyFromPhysical(void* to, phys_addr_t from,
151									size_t length, bool user);
152	virtual	status_t			MemcpyToPhysical(phys_addr_t to,
153									const void* from, size_t length, bool user);
154	virtual	void				MemcpyPhysicalPage(phys_addr_t to,
155									phys_addr_t from);
156
157			status_t			GetSlot(bool canWait,
158									PhysicalPageSlot*& slot);
159			void				PutSlot(PhysicalPageSlot* slot);
160
161	inline	PhysicalPageSlotQueue* GetSlotQueue(int32 cpu, bool user);
162
163private:
164	typedef DoublyLinkedList<PhysicalPageSlotPool> PoolList;
165
166			mutex				fLock;
167			PoolList			fEmptyPools;
168			PoolList			fNonEmptyPools;
169			PhysicalPageSlot* fDebugSlot;
170			PhysicalPageSlotPool* fInitialPool;
171			LargeMemoryTranslationMapPhysicalPageMapper	fKernelMapper;
172			PhysicalPageOpsCPUData fPerCPUData[SMP_MAX_CPUS];
173};
174
175static LargeMemoryPhysicalPageMapper sPhysicalPageMapper;
176
177
178// #pragma mark - PhysicalPageSlot / PhysicalPageSlotPool
179
180
181inline void
182PhysicalPageSlot::Map(phys_addr_t physicalAddress)
183{
184	pool->Map(physicalAddress, address);
185}
186
187
188PhysicalPageSlotPool::~PhysicalPageSlotPool()
189{
190}
191
192
193inline bool
194PhysicalPageSlotPool::IsEmpty() const
195{
196	return fSlots == NULL;
197}
198
199
200inline PhysicalPageSlot*
201PhysicalPageSlotPool::GetSlot()
202{
203	PhysicalPageSlot* slot = fSlots;
204	fSlots = slot->next;
205	return slot;
206}
207
208
209inline void
210PhysicalPageSlotPool::PutSlot(PhysicalPageSlot* slot)
211{
212	slot->next = fSlots;
213	fSlots = slot;
214}
215
216
217// #pragma mark - PhysicalPageSlotQueue
218
219
220PhysicalPageSlotQueue::PhysicalPageSlotQueue()
221	:
222	fSlots(NULL)
223{
224	fFreeSlotCondition.Init(this, "physical page ops slot queue");
225	fFreeSlotsCondition.Init(this, "physical page ops slots queue");
226}
227
228
229PhysicalPageSlot*
230PhysicalPageSlotQueue::GetSlot()
231{
232	InterruptsLocker locker;
233
234	// wait for a free slot to turn up
235	while (fSlots == NULL) {
236		ConditionVariableEntry entry;
237		fFreeSlotCondition.Add(&entry);
238		locker.Unlock();
239		entry.Wait();
240		locker.Lock();
241	}
242
243	PhysicalPageSlot* slot = fSlots;
244	fSlots = slot->next;
245
246	return slot;
247}
248
249
250void
251PhysicalPageSlotQueue::GetSlots(PhysicalPageSlot*& slot1,
252	PhysicalPageSlot*& slot2)
253{
254	InterruptsLocker locker;
255
256	// wait for two free slot to turn up
257	while (fSlots == NULL || fSlots->next == NULL) {
258		ConditionVariableEntry entry;
259		fFreeSlotsCondition.Add(&entry);
260		locker.Unlock();
261		entry.Wait();
262		locker.Lock();
263	}
264
265	slot1 = fSlots;
266	slot2 = slot1->next;
267	fSlots = slot2->next;
268}
269
270
271void
272PhysicalPageSlotQueue::PutSlot(PhysicalPageSlot* slot)
273{
274	InterruptsLocker locker;
275
276	slot->next = fSlots;
277	fSlots = slot;
278
279	if (slot->next == NULL)
280		fFreeSlotCondition.NotifyAll();
281	else if (slot->next->next == NULL)
282		fFreeSlotCondition.NotifyAll();
283}
284
285
286void
287PhysicalPageSlotQueue::PutSlots(PhysicalPageSlot* slot1,
288	PhysicalPageSlot* slot2)
289{
290	InterruptsLocker locker;
291
292	slot1->next = slot2;
293	slot2->next = fSlots;
294	fSlots = slot1;
295
296	if (slot2->next == NULL)
297		fFreeSlotCondition.NotifyAll();
298	else if (slot2->next->next == NULL)
299		fFreeSlotCondition.NotifyAll();
300}
301
302
303// #pragma mark - PhysicalPageOpsCPUData
304
305
306void
307PhysicalPageOpsCPUData::Init()
308{
309	for (int32 i = 0; i < USER_SLOTS_PER_CPU; i++)
310		user.PutSlot(_GetInitialSlot());
311	for (int32 i = 0; i < KERNEL_SLOTS_PER_CPU; i++)
312		kernel.PutSlot(_GetInitialSlot());
313	interruptSlot = _GetInitialSlot();
314}
315
316
317/* static */ PhysicalPageSlot*
318PhysicalPageOpsCPUData::_GetInitialSlot()
319{
320	PhysicalPageSlot* slot;
321	status_t error = sPhysicalPageMapper.GetSlot(false, slot);
322	if (error != B_OK) {
323		panic("PhysicalPageOpsCPUData::Init(): Failed to get initial "
324			"physical page slots! Probably too many CPUs.");
325		return NULL;
326	}
327
328	return slot;
329}
330
331
332// #pragma mark - LargeMemoryTranslationMapPhysicalPageMapper
333
334
335LargeMemoryTranslationMapPhysicalPageMapper
336	::LargeMemoryTranslationMapPhysicalPageMapper()
337	:
338	fSlotCount(sizeof(fSlots) / sizeof(page_slot)),
339	fNextSlot(0)
340{
341	memset(fSlots, 0, sizeof(fSlots));
342}
343
344
345LargeMemoryTranslationMapPhysicalPageMapper
346	::~LargeMemoryTranslationMapPhysicalPageMapper()
347{
348	// put our slots back to the global pool
349	for (int32 i = 0; i < fSlotCount; i++) {
350		if (fSlots[i].slot != NULL)
351			sPhysicalPageMapper.PutSlot(fSlots[i].slot);
352	}
353}
354
355
356status_t
357LargeMemoryTranslationMapPhysicalPageMapper::Init()
358{
359	// get our slots from the global pool
360	for (int32 i = 0; i < fSlotCount; i++) {
361		status_t error = sPhysicalPageMapper.GetSlot(true, fSlots[i].slot);
362		if (error != B_OK)
363			return error;
364
365		// set to invalid physical address, so it won't be used accidentally
366		fSlots[i].physicalAddress = ~(phys_addr_t)0;
367	}
368
369	return B_OK;
370}
371
372
373void
374LargeMemoryTranslationMapPhysicalPageMapper::Delete()
375{
376	delete this;
377}
378
379
380void*
381LargeMemoryTranslationMapPhysicalPageMapper::GetPageTableAt(
382	phys_addr_t physicalAddress)
383{
384	ASSERT(physicalAddress % B_PAGE_SIZE == 0);
385
386	int32 currentCPU = smp_get_current_cpu();
387
388	// maybe the address is already mapped
389	for (int32 i = 0; i < fSlotCount; i++) {
390		page_slot& slot = fSlots[i];
391		if (slot.physicalAddress == physicalAddress) {
392			fNextSlot = (i + 1) & (fSlotCount - 1);
393			if (!slot.valid.GetBit(currentCPU)) {
394				// not valid on this CPU -- invalidate the TLB entry
395				invalidate_TLB(slot.slot->address);
396				slot.valid.SetBit(currentCPU);
397			}
398			return (void*)slot.slot->address;
399		}
400	}
401
402	// not found -- need to map a fresh one
403	page_slot& slot = fSlots[fNextSlot];
404	fNextSlot = (fNextSlot + 1) & (fSlotCount - 1);
405
406	slot.physicalAddress = physicalAddress;
407	slot.slot->Map(physicalAddress);
408	slot.valid.ClearAll();
409	slot.valid.SetBit(currentCPU);
410
411	return (void*)slot.slot->address;
412}
413
414
415// #pragma mark - LargeMemoryPhysicalPageMapper
416
417
418LargeMemoryPhysicalPageMapper::LargeMemoryPhysicalPageMapper()
419	:
420	fInitialPool(NULL)
421{
422	mutex_init(&fLock, "large memory physical page mapper");
423}
424
425
426status_t
427LargeMemoryPhysicalPageMapper::Init(kernel_args* args,
428	PhysicalPageSlotPool* initialPools, int32 initialPoolCount, size_t poolSize,
429	TranslationMapPhysicalPageMapper*& _kernelPageMapper)
430{
431	ASSERT(initialPoolCount >= 1);
432
433	fInitialPool = initialPools;
434	for (int32 i = 0; i < initialPoolCount; i++) {
435		uint8* pointer = (uint8*)initialPools + i * poolSize;
436		fNonEmptyPools.Add((PhysicalPageSlotPool*)pointer);
437	}
438
439	// get the debug slot
440	GetSlot(true, fDebugSlot);
441
442	// init the kernel translation map physical page mapper
443	status_t error = fKernelMapper.Init();
444	if (error != B_OK) {
445		panic("LargeMemoryPhysicalPageMapper::Init(): Failed to init "
446			"kernel translation map physical page mapper!");
447		return error;
448	}
449	_kernelPageMapper = &fKernelMapper;
450
451	// init the per-CPU data
452	int32 cpuCount = smp_get_num_cpus();
453	for (int32 i = 0; i < cpuCount; i++)
454		fPerCPUData[i].Init();
455
456	return B_OK;
457}
458
459
460status_t
461LargeMemoryPhysicalPageMapper::CreateTranslationMapPhysicalPageMapper(
462	TranslationMapPhysicalPageMapper** _mapper)
463{
464	LargeMemoryTranslationMapPhysicalPageMapper* mapper
465		= new(std::nothrow) LargeMemoryTranslationMapPhysicalPageMapper;
466	if (mapper == NULL)
467		return B_NO_MEMORY;
468
469	status_t error = mapper->Init();
470	if (error != B_OK) {
471		delete mapper;
472		return error;
473	}
474
475	*_mapper = mapper;
476	return B_OK;
477}
478
479
480void*
481LargeMemoryPhysicalPageMapper::InterruptGetPageTableAt(
482	phys_addr_t physicalAddress)
483{
484	ASSERT(physicalAddress % B_PAGE_SIZE == 0);
485
486	PhysicalPageSlot* slot = fPerCPUData[smp_get_current_cpu()].interruptSlot;
487	slot->Map(physicalAddress);
488	return (void*)slot->address;
489}
490
491
492status_t
493LargeMemoryPhysicalPageMapper::GetPage(phys_addr_t physicalAddress,
494	addr_t* virtualAddress, void** handle)
495{
496	PhysicalPageSlot* slot = NULL;
497	status_t error = GetSlot(true, slot);
498	if (error != B_OK)
499		return error;
500
501	slot->Map(physicalAddress);
502
503	*handle = slot;
504	*virtualAddress = slot->address + physicalAddress % B_PAGE_SIZE;
505
506	smp_send_broadcast_ici(SMP_MSG_INVALIDATE_PAGE_RANGE, *virtualAddress,
507		*virtualAddress, 0, NULL, SMP_MSG_FLAG_SYNC);
508
509	return B_OK;
510}
511
512
513status_t
514LargeMemoryPhysicalPageMapper::PutPage(addr_t virtualAddress, void* handle)
515{
516	PutSlot((PhysicalPageSlot*)handle);
517	return B_OK;
518}
519
520
521status_t
522LargeMemoryPhysicalPageMapper::GetPageCurrentCPU(phys_addr_t physicalAddress,
523	addr_t* virtualAddress, void** handle)
524{
525	// get a slot from the per-cpu user pool
526	PhysicalPageSlotQueue& slotQueue
527		= fPerCPUData[smp_get_current_cpu()].user;
528	PhysicalPageSlot* slot = slotQueue.GetSlot();
529	slot->Map(physicalAddress);
530
531	*virtualAddress = slot->address + physicalAddress % B_PAGE_SIZE;
532	*handle = slot;
533
534	return B_OK;
535}
536
537
538status_t
539LargeMemoryPhysicalPageMapper::PutPageCurrentCPU(addr_t virtualAddress,
540	void* handle)
541{
542	// return the slot to the per-cpu user pool
543	PhysicalPageSlotQueue& slotQueue
544		= fPerCPUData[smp_get_current_cpu()].user;
545	slotQueue.PutSlot((PhysicalPageSlot*)handle);
546	return B_OK;
547}
548
549
550status_t
551LargeMemoryPhysicalPageMapper::GetPageDebug(phys_addr_t physicalAddress,
552	addr_t* virtualAddress, void** handle)
553{
554	fDebugSlot->Map(physicalAddress);
555
556	*handle = fDebugSlot;
557	*virtualAddress = fDebugSlot->address + physicalAddress % B_PAGE_SIZE;
558	return B_OK;
559}
560
561
562status_t
563LargeMemoryPhysicalPageMapper::PutPageDebug(addr_t virtualAddress, void* handle)
564{
565	return B_OK;
566}
567
568
569status_t
570LargeMemoryPhysicalPageMapper::MemsetPhysical(phys_addr_t address, int value,
571	phys_size_t length)
572{
573	addr_t pageOffset = address % B_PAGE_SIZE;
574
575	Thread* thread = thread_get_current_thread();
576	ThreadCPUPinner _(thread);
577
578	PhysicalPageSlotQueue* slotQueue = GetSlotQueue(thread->cpu->cpu_num,
579		false);
580	PhysicalPageSlot* slot = slotQueue->GetSlot();
581
582	while (length > 0) {
583		slot->Map(address - pageOffset);
584
585		size_t toSet = min_c(length, B_PAGE_SIZE - pageOffset);
586		memset((void*)(slot->address + pageOffset), value, toSet);
587
588		length -= toSet;
589		address += toSet;
590		pageOffset = 0;
591	}
592
593	slotQueue->PutSlot(slot);
594
595	return B_OK;
596}
597
598
599status_t
600LargeMemoryPhysicalPageMapper::MemcpyFromPhysical(void* _to, phys_addr_t from,
601	size_t length, bool user)
602{
603	uint8* to = (uint8*)_to;
604	addr_t pageOffset = from % B_PAGE_SIZE;
605
606	Thread* thread = thread_get_current_thread();
607	ThreadCPUPinner _(thread);
608
609	PhysicalPageSlotQueue* slotQueue = GetSlotQueue(thread->cpu->cpu_num, user);
610	PhysicalPageSlot* slot = slotQueue->GetSlot();
611
612	status_t error = B_OK;
613
614	while (length > 0) {
615		size_t toCopy = min_c(length, B_PAGE_SIZE - pageOffset);
616
617		slot->Map(from - pageOffset);
618
619		if (user) {
620			error = user_memcpy(to, (void*)(slot->address + pageOffset),
621				toCopy);
622			if (error != B_OK)
623				break;
624		} else
625			memcpy(to, (void*)(slot->address + pageOffset), toCopy);
626
627		to += toCopy;
628		from += toCopy;
629		length -= toCopy;
630		pageOffset = 0;
631	}
632
633	slotQueue->PutSlot(slot);
634
635	return error;
636}
637
638
639status_t
640LargeMemoryPhysicalPageMapper::MemcpyToPhysical(phys_addr_t to,
641	const void* _from, size_t length, bool user)
642{
643	const uint8* from = (const uint8*)_from;
644	addr_t pageOffset = to % B_PAGE_SIZE;
645
646	Thread* thread = thread_get_current_thread();
647	ThreadCPUPinner _(thread);
648
649	PhysicalPageSlotQueue* slotQueue = GetSlotQueue(thread->cpu->cpu_num, user);
650	PhysicalPageSlot* slot = slotQueue->GetSlot();
651
652	status_t error = B_OK;
653
654	while (length > 0) {
655		size_t toCopy = min_c(length, B_PAGE_SIZE - pageOffset);
656
657		slot->Map(to - pageOffset);
658
659		if (user) {
660			error = user_memcpy((void*)(slot->address + pageOffset), from,
661				toCopy);
662			if (error != B_OK)
663				break;
664		} else
665			memcpy((void*)(slot->address + pageOffset), from, toCopy);
666
667		to += toCopy;
668		from += toCopy;
669		length -= toCopy;
670		pageOffset = 0;
671	}
672
673	slotQueue->PutSlot(slot);
674
675	return error;
676}
677
678
679void
680LargeMemoryPhysicalPageMapper::MemcpyPhysicalPage(phys_addr_t to,
681	phys_addr_t from)
682{
683	Thread* thread = thread_get_current_thread();
684	ThreadCPUPinner _(thread);
685
686	PhysicalPageSlotQueue* slotQueue = GetSlotQueue(thread->cpu->cpu_num,
687		false);
688	PhysicalPageSlot* fromSlot;
689	PhysicalPageSlot* toSlot;
690	slotQueue->GetSlots(fromSlot, toSlot);
691
692	fromSlot->Map(from);
693	toSlot->Map(to);
694
695	memcpy((void*)toSlot->address, (void*)fromSlot->address, B_PAGE_SIZE);
696
697	slotQueue->PutSlots(fromSlot, toSlot);
698}
699
700
701status_t
702LargeMemoryPhysicalPageMapper::GetSlot(bool canWait, PhysicalPageSlot*& slot)
703{
704	MutexLocker locker(fLock);
705
706	PhysicalPageSlotPool* pool = fNonEmptyPools.Head();
707	if (pool == NULL) {
708		if (!canWait)
709			return B_WOULD_BLOCK;
710
711		// allocate new pool
712		locker.Unlock();
713		status_t error = fInitialPool->AllocatePool(pool);
714		if (error != B_OK)
715			return error;
716		locker.Lock();
717
718		fNonEmptyPools.Add(pool);
719		pool = fNonEmptyPools.Head();
720	}
721
722	slot = pool->GetSlot();
723
724	if (pool->IsEmpty()) {
725		fNonEmptyPools.Remove(pool);
726		fEmptyPools.Add(pool);
727	}
728
729	return B_OK;
730}
731
732
733void
734LargeMemoryPhysicalPageMapper::PutSlot(PhysicalPageSlot* slot)
735{
736	MutexLocker locker(fLock);
737
738	PhysicalPageSlotPool* pool = slot->pool;
739	if (pool->IsEmpty()) {
740		fEmptyPools.Remove(pool);
741		fNonEmptyPools.Add(pool);
742	}
743
744	pool->PutSlot(slot);
745}
746
747
748inline PhysicalPageSlotQueue*
749LargeMemoryPhysicalPageMapper::GetSlotQueue(int32 cpu, bool user)
750{
751	return user ? &fPerCPUData[cpu].user : &fPerCPUData[cpu].kernel;
752}
753
754
755// #pragma mark - Initialization
756
757
758status_t
759large_memory_physical_page_ops_init(kernel_args* args,
760	X86LargePhysicalPageMapper::PhysicalPageSlotPool* initialPools,
761	int32 initialPoolCount, size_t poolSize,
762	X86PhysicalPageMapper*& _pageMapper,
763	TranslationMapPhysicalPageMapper*& _kernelPageMapper)
764{
765	new(&sPhysicalPageMapper) LargeMemoryPhysicalPageMapper;
766	sPhysicalPageMapper.Init(args, initialPools, initialPoolCount, poolSize,
767		_kernelPageMapper);
768
769	_pageMapper = &sPhysicalPageMapper;
770	return B_OK;
771}
772