информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
Страшный баг в WindowsАтака на InternetЗа кого нас держат?
BugTraq.Ru
Русский BugTraq
 Анализ криптографических сетевых... 
 Модель надежности двухузлового... 
 Специальные марковские модели надежности... 
 И ещё раз об интернет-голосовании 
 Типовые уязвимости в драйверах... 
 Logitech готовится закрыть очередную... 
главная обзор RSN блог библиотека закон бред форум dnet о проекте
bugtraq.ru / форум / programming
Имя Пароль
ФОРУМ
если вы видите этот текст, отключите в настройках форума использование JavaScript
регистрация





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
Хм. Интересно а в чем логика? Я то уж было ломанулся... 28.03.09 05:53  Число просмотров: 1528
Автор: amirul <Serge> Статус: The Elderman
<"чистая" ссылка>
> UPD: Забыл сказать - доступ к элементу пула должет быть
> именно по индексу, а не по адресу обекта пула. Поэтому
> одного SLIST (когда бы Index_in_pool включал бы указатель
> на ptr = new Pool_entry_t() вместо индекса) без
> Pool_entry_t m_pool[pool_size] недостаточно. Это часть
> бизнес логики.

Хм. Интересно а в чем логика? Я то уж было ломанулся исправлять явно лишнее индексирование :-)

А вообще только что пришла идея: для каждого процессора выделить свой лист свободных индексов. Если выделение произошло на одном процессоре, а возврат на другом - это ожидаемо и нормально. Если пул у какого нибудь процессора закончится, то тогда уж и делать stop-the-world и балансировать пулы, предполагается, что если выделения/освобождения распределены более менее равномерно, то листы свободных индексов для каждого процессора будут примерно равными по длине.

Осталось найти недорогой способ получения номера текущего процессора, но думаю это непривилегированная операция и может быть выполнена без ухода в ядро. Кроме того, нужно придумать способ лочить очередь без захвата шины (уже в однопроцессорном окружении), но на мой взгляд это довольно легко.

Ну и после всех этих манипуляций придется проверять дают ли они хоть какой то выигрыш :-)
<programming>
[C++] UPD: супер простой и супербыстрый pool 28.03.09 03:30  
Автор: void <Grebnev Valery> Статус: Elderman
Отредактировано 28.03.09 05:02  Количество правок: 1
<"чистая" ссылка>
UPD: Забыл сказать - доступ к элементу пула должет быть именно по индексу, а не по адресу обекта пула. Поэтому одного SLIST (когда бы Index_in_pool включал бы указатель на ptr = new Pool_entry_t() вместо индекса) без Pool_entry_t m_pool[pool_size] недостаточно. Это часть бизнес логики.

Ищется таковой. Чтобы было просто, и самое главное работало быстро (без высокого контеншн) для 5-10 thread-ов на multi-core box. Самое тривиальное, что приходит на ум - ниже. Сейчас очень модно lock-free решения. Может кто подскажет альтернативу тому, что ниже?

template <typename Pool_entry_t, size_t pool_size> 
class Pool_t
{
public:
	Pool_t()
	{
		::InitializeSListHead(&m_pool_index_head);
		for(size_t i = 0; i < pool_size; i++)
		{
			Index_in_pool* pindex = new Index_in_pool(i);
			::InterlockedPushEntrySList(&m_pool_index_head, pindex);
		}
	}
	~Pool_t()
	{
		::InterlockedFlushSList(&m_pool_index_head);
	}
	typedef SLIST_HEADER DECLSPEC_ALIGN(MEMORY_ALLOCATION_ALIGNMENT) SLIST_HEADER_;
	struct DECLSPEC_ALIGN(MEMORY_ALLOCATION_ALIGNMENT) Index_in_pool: SLIST_ENTRY
	{
		size_t m_index;
		Index_in_pool(size_t index): m_index(index){}
		void* operator new(size_t)
		{
			void*p = ::_aligned_malloc(sizeof(Index_in_pool),MEMORY_ALLOCATION_ALIGNMENT);
			if (p == NULL)
			{
				::RaiseException( STATUS_NONCONTINUABLE_EXCEPTION, 0, 0, 0);
			}
			else
			{
			}
			return p;
		}
		void operator delete (void *p)
		{	
			::_aligned_free(p);
		}
	};

	Index_in_pool* alloc_entry(void)
	{
		return (Index_in_pool*) ::InterlockedPopEntrySList(&m_pool_index_head);
	}
	void release_entry(Index_in_pool* pentry)
	{
		::InterlockedPushEntrySList(&m_pool_index_head, pentry);
	}
	Pool_entry_t* get_entry(size_t index)
	{
		return m_pool + index;
	}

	Pool_entry_t m_pool[pool_size];
	SLIST_HEADER_ m_pool_index_head;
};

---

Использовать приблизительно так:

Pool_t<test_buffer, 5> g_buffer_pool;
bool simulate_pool_work(void)
{
	Pool_t<test_buffer, 5>::Index_in_pool* pentry = g_buffer_pool.alloc_entry();

	test_buffer* ptr_buffer = g_buffer_pool.get_entry(pentry->m_index);

	for (int i = 0; i < 1; i++)
	{
		ptr_buffer->write();
		if (!ptr_buffer->read())
		{
			return false;
		}
		else
		{
		}
	}

	g_buffer_pool.release_entry(pentry);
	return true;
}

---
Хм. Интересно а в чем логика? Я то уж было ломанулся... 28.03.09 05:53  
Автор: amirul <Serge> Статус: The Elderman
<"чистая" ссылка>
> UPD: Забыл сказать - доступ к элементу пула должет быть
> именно по индексу, а не по адресу обекта пула. Поэтому
> одного SLIST (когда бы Index_in_pool включал бы указатель
> на ptr = new Pool_entry_t() вместо индекса) без
> Pool_entry_t m_pool[pool_size] недостаточно. Это часть
> бизнес логики.

Хм. Интересно а в чем логика? Я то уж было ломанулся исправлять явно лишнее индексирование :-)

А вообще только что пришла идея: для каждого процессора выделить свой лист свободных индексов. Если выделение произошло на одном процессоре, а возврат на другом - это ожидаемо и нормально. Если пул у какого нибудь процессора закончится, то тогда уж и делать stop-the-world и балансировать пулы, предполагается, что если выделения/освобождения распределены более менее равномерно, то листы свободных индексов для каждого процессора будут примерно равными по длине.

Осталось найти недорогой способ получения номера текущего процессора, но думаю это непривилегированная операция и может быть выполнена без ухода в ядро. Кроме того, нужно придумать способ лочить очередь без захвата шины (уже в однопроцессорном окружении), но на мой взгляд это довольно легко.

Ну и после всех этих манипуляций придется проверять дают ли они хоть какой то выигрыш :-)
В принципе достаточно много задач, где нужно клиенту... 28.03.09 06:25  
Автор: void <Grebnev Valery> Статус: Elderman
Отредактировано 28.03.09 06:26  Количество правок: 1
<"чистая" ссылка>
> Хм. Интересно а в чем логика? Я то уж было ломанулся
> исправлять явно лишнее индексирование :-)

В принципе достаточно много задач, где нужно клиенту отдавать индекс, а не адрес. В той задаче, для которой это сейчас делается - для храния имеетсятолько WORD. Получив новый объект из пула, клиент будет проводить типа CAS над этим индексом, чтобы удостовериться, что использует один и тот же shared буфер, который уже захвачен другим клиентом. Типа как общий объект, буфер, и т.д для нескольких клиентов. Другого рода задачи всплывают в IPC на shared memory, когда сервер отдаёт клиенту "номер" shared канала. Можно конечно, получив ::InterlockedPopEntrySList адрес затем мапить или хеш мапить его на индекс, но это может быть не бесплатно. Хотя конечно надо тестировать.

> А вообще только что пришла идея: для каждого процессора
> выделить свой лист свободных индексов.

Идея хорошая и не только для данной задачи. Надо об этом подумать ;-)

> Кроме того, нужно
> придумать способ лочить очередь без захвата шины (уже в
> однопроцессорном окружении), но на мой взгляд это довольно
> легко.

А как? ... Саттер не так давно написал нескольно статей по этому поводу. Но я признаться не смотрел.
Саттера не читал, но мнение имею [upd] 28.03.09 08:48  
Автор: amirul <Serge> Статус: The Elderman
Отредактировано 28.03.09 09:14  Количество правок: 1
<"чистая" ссылка>
> > Кроме того, нужно
> > придумать способ лочить очередь без захвата шины (уже
> в
> > однопроцессорном окружении), но на мой взгляд это
> довольно
> > легко.
>
> А как? ... Саттер не так давно написал нескольно статей по
> этому поводу. Но я признаться не смотрел.

Саттера не читал, но мнение имею

Вообще интуиция подсказывает, что обычный CMPXCHG (без префикса LOCK) - должен отлично сработать. Я могу ошибаться, но насколько я понимаю поток может быть вытеснен только между инструкциями, а не прямо посреди (если прерывание приходит посреди инструкции, то процессор дожидается окончания этой инструкции) - а для однопроцессорной среды этого достаточно для обеспечения атомарности. Соответственно, когда флаг, блокирующий очередь для процессора (одна очередь - один флаг) не получается "захватить" - отдаем квант чем то вроде sleep(0) или подобным и делаем спин. Огромная стоимость такой операции для ожидающего потока будет нивелироваться крайне низкой вероятностью рейса на участке из десятка инструкций (pop из односвязного списка и освобождение очереди).

-------------------
Кстати, о текущем процессоре. В Win2k3 появилась полезная функция GetCurrentProcessorNumber. Вот так выглядит версия из Win7 (в других скорее всего что то подобное):

ntdll!RtlGetCurrentProcessorNumberEx:
7787cab6 8bff            mov     edi,edi
7787cab8 55              push    ebp
7787cab9 8bec            mov     ebp,esp
7787cabb 8b5508          mov     edx,dword ptr [ebp+8]
7787cabe 33c0            xor     eax,eax
7787cac0 668902          mov     word ptr [edx],ax
7787cac3 b93b000000      mov     ecx,3Bh
7787cac8 0f03c1          lsl     eax,ecx
7787cacb c1e80e          shr     eax,0Eh
7787cace 884202          mov     byte ptr [edx+2],al
7787cad1 c6420300        mov     byte ptr [edx+3],0
7787cad5 5d              pop     ebp
7787cad6 c20400          ret     4

---

Передается туда указатель на структуру:
typedef struct _PROCESSOR_NUMBER {
  WORD Group;
  BYTE Number;
  BYTE Reserved;
} PROCESSOR_NUMBER, *PPROCESSOR_NUMBER;

---

Так что болдом выделено конкретно получение номера процессора. Висты сейчас под рукой нет - проверить не могу, но как я уже сказал вряд ли она уходит в ядро, так что можно смело использовать эту функцию - оверхед на IPI и коллизии по идее должен быть больше. Так что можно сделать более продуктивную версию для 2k3+ с откатом к бейскейс реализации на interlocked-очереди для 2k/xp
1






Rambler's Top100
Рейтинг@Mail.ru


  Copyright © 2001-2019 Dmitry Leonov   Page build time: 0 s   Design: Vadim Derkach