Musannaf Ibn Abi Shayba 1:1283

Waki’ narrated to us, from al-A’mash, from Ibrahim, from Alqama, that he used to command his women to dye themselves with henna during the days of their menstruation.